662. Maximum Width of Binary Tree

https://leetcode.com/problems/maximum-width-of-binary-tree/

Maximum Width of Binary Tree - LeetCode

root -> left (x2)

root -> right (x2 +1)

 

44ms

# 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

import collections

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        
        root.val = 1
        dummy = TreeNode(val=None)
        q = collections.deque([root, dummy])
        
        res = 1
        
        _min = float('inf')
        _max = float('-inf')
        
        while q:
            node = q.popleft()
            
            if node == dummy:
                if not q:
                    break
                res = max(res, _max-_min+1)
                q.append(dummy)
                _min = float('inf')
                _max = float('-inf')
                continue
            
            if node.left:
                node.left.val = node.val*2
                _min = min(_min, node.left.val)
                _max = max(_max, node.left.val)
                q.append(node.left)
                
            if node.right:
                node.right.val = node.val*2+1
                _min = min(_min, node.right.val)
                _max = max(_max, node.right.val)
                q.append(node.right)
            
        return res

28ms

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        queue = collections.deque([(root, 0, 0)])
        currDepth = left = ans = 0
        while queue:
            node, depth, pos = queue.popleft()
            if node:
                queue.append((node.left, depth + 1, pos*2))
                queue.append((node.right, depth + 1, pos*2+1))
                if currDepth != depth:
                    currDepth = depth
                    left = pos
                ans = max(ans, pos - left + 1)
        return ans