662. Maximum Width of Binary Tree

Problem Statement

link: LeetCode.cn LeetCode Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example:

Input: root = [1,3,2,5,3,null,9] Output: 4

Input: root = [1,3,2,5,null,null,9,6,null,7] Output: 7

Input: root = [1,3,2,5] Output: 2

Solution Approach

The solution utilizes breadth-first search (BFS) to traverse the binary tree level by level, keeping track of the positions of nodes. It calculates the width of each level by considering the positions of the leftmost and rightmost nodes, and updates the maximum width accordingly.

Algorithm

1. Initialization: Start with a queue containing the root node and its position (usually starting with 0). Initialize a variable to store the maximum width found so far, initially set to 1.
2. BFS Traversal: Perform a breadth-first search (BFS) traversal of the binary tree. At each level of the tree, calculate the width by subtracting the positions of the leftmost and rightmost nodes. Update the maximum width if the current width is greater than the previously recorded maximum.
3. Update Queue: As you traverse each level, update the queue with the children nodes and their corresponding positions. Use a temporary list to store the next level’s nodes and their positions. Continue this process until the queue is empty and all levels have been traversed. Return the maximum width found.

Implement

    # Definition for a binary tree node. # class TreeNode: #     def __init__(self, val=0, left=None, right=None): #         self.val = val #         self.left = left #         self.right = right class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 1
        q = [(root, 0)]
        while q:
            res = max(res, q[-1][1] - q[0][1] + 1)
            temp = []
            for node, pos in q:
                if node.left:
                    temp.append((node.left, pos * 2))
                if node.right:
                    temp.append((node.right, pos * 2 + 1))
            q = temp
        return res

              

    
    

Twitter  facebook  Email