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 1:
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
Example 2:
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
Example 3:
Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).
Constraints:
The number of nodes in the tree is in the range [1, 3000].
-100 <= Node.val <= 100
Solutions
Solution 1
1 2 3 4 5 6 7 8 910111213141516171819
# 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 = rightclassSolution:defwidthOfBinaryTree(self,root:Optional[TreeNode])->int:ans=0q=deque([(root,1)])whileq:ans=max(ans,q[-1][1]-q[0][1]+1)for_inrange(len(q)):root,i=q.popleft()ifroot.left:q.append((root.left,i<<1))ifroot.right:q.append((root.right,i<<1|1))returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcwidthOfBinaryTree(root*TreeNode)int{q:=[]pair{{root,1}}ans:=0forlen(q)>0{ans=max(ans,q[len(q)-1].i-q[0].i+1)forn:=len(q);n>0;n--{p:=q[0]q=q[1:]root=p.nodeifroot.Left!=nil{q=append(q,pair{root.Left,p.i<<1})}ifroot.Right!=nil{q=append(q,pair{root.Right,p.i<<1|1})}}}returnans}typepairstruct{node*TreeNodeiint}
Solution 2
1 2 3 4 5 6 7 8 91011121314151617181920212223
# 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 = rightclassSolution:defwidthOfBinaryTree(self,root:Optional[TreeNode])->int:defdfs(root,depth,i):ifrootisNone:returniflen(t)==depth:t.append(i)else:nonlocalansans=max(ans,i-t[depth]+1)dfs(root.left,depth+1,i<<1)dfs(root.right,depth+1,i<<1|1)ans=1t=[]dfs(root,0,1)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcwidthOfBinaryTree(root*TreeNode)int{ans:=1t:=[]int{}vardfsfunc(root*TreeNode,depth,iint)dfs=func(root*TreeNode,depth,iint){ifroot==nil{return}iflen(t)==depth{t=append(t,i)}else{ans=max(ans,i-t[depth]+1)}dfs(root.Left,depth+1,i<<1)dfs(root.Right,depth+1,i<<1|1)}dfs(root,0,1)returnans}