we use BFS or level order traversal.we keep tarck of level,index of each node in queue for calculating max width.
Algorithm:
1.if root=null;return 0
2.create a queue to store the index,level,TreeNode
3.we fill indexes according to the following
indexof_leftchild = (2*(index_of_root))
indexof_rightchild = (2*(index_of_root)+1)
4.we pop the first item in queue and check for level if cur_level > prev_level we update them
5.maximum width will be max(prev_width,(cur_idx-idx_old)+1)
6.return maxwidth
TimeComplexity:O(N)
SpaceComplexity:O(N)
Python Code:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def widthOfBinaryTree(self, root):
prev_level, idx_old, result = 1, 1, 0
queue = [[prev_level,idx_old,root]]
while queue:
[cur_idx, cur_level, node] = queue.pop(0)
if cur_level > prev_level:
prev_level, idx_old = cur_level, cur_idx
result = max(result, cur_idx - idx_old + 1)
if node.left: queue.append([cur_idx*2, cur_level+1, node.left])
if node.right: queue.append([cur_idx*2+1,cur_level+1, node.right])
return result
0 Comments