Maximum Width of Binary Tree
Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.
The width of one level is defined as the length between the end-nodes
(the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.
Example 1:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: 4
Explanation: The maximum width existing in the third level with the length 4
(5,3,null,9).
Example 2:
Input:
1
/
3
/ \
5 3
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input:
1
/ \
3 2
/
5
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input:
1
/ \
3 2
/ \
5 9
/ \
6 7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8
(6,null,null,null,null,null,null,7).
Note: Answer will in the range of 32-bit signed integer.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> nodes = new LinkedList<>();
nodes.offer(root);
root.val = 0;
int max = 1;
while (!nodes.isEmpty()) {
int size = nodes.size();
max = Math.max(max, nodes.peekLast().val - nodes.peekFirst().val + 1);
for (int i = 0; i < size; i++) {
root = nodes.poll();
if (root.left != null) {
root.left.val = root.val * 2;
nodes.offer(root.left);
}
if (root.right != null) {
root.right.val = root.val * 2 + 1;
nodes.offer(root.right);
}
}
}
return max;
}
}
Here, we are going to solve by changing given values to find maximum width. The main idea to solve this approach is regardless of any nodes,
1) Always make value of left child as parent_index * 2
2) Always make value of right child as parent_index * 2 + 1
3) We are going to repeat above steps till end of binary tree.
4) While repeating above steps at the same time we are updating max using Math.max(max, last node value - first node value +1)
5) Finally after reaching end of tree, return max which will be output we needed.
Example:
Input Updated Tree using Step 1, 2
1 0 Max = 1(Initially)
/ \ / \
3 2 0 1 Max = 2
/ \ \ / \ \
5 3 9 0 1 3 Max = 4
Comments
Post a Comment