python - max width of a tree


  • 0
    S
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def widthOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            queue, answer = [(root, 0)], 0
            while queue:
                
                L, R = queue[0][1], queue[-1][1]
                answer = max(answer, R-L+1)
                
                tmpq = []
                for node, pos in queue:
                    if node.left: tmpq.append((node.left, pos * 2))
                    if node.right: tmpq.append((node.right, pos * 2 + 1))
                    
                queue = tmpq
            
            return answer
                        
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.