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(int x) { val = x; } * } */ class Solution { public int widthOfBinaryTree(TreeNode root) { if (root == null) return 0; int re = 1; Queue<TreeNode> data = new LinkedList<>(); data.add(root); while (!data.isEmpty()) { int n = data.size(); int cur = 0; int count = 0; while (n-- > 0) { TreeNode tn = data.poll(); if (tn.left != null) { if (count != 0) { count = count + cur + 1; while (cur-- > 0) data.add(new TreeNode(-1)); } else count += 1; cur = 0; data.add(tn.left); } else { cur++; } if (tn.right != null) { if (count != 0) { count = count + cur + 1; while (cur-- > 0) data.add(new TreeNode(-1)); } else count += 1; cur = 0; data.add(tn.right); } else { cur++; } } re = re >= count ? re : count; } return re; } }
