原题链接在这里：https://leetcode.com/problems/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.
题解：
把每个点笔记上id. cur.id = i, 那么cur.left.id = 2*i, cur.right.id = 2*i+1.
找到每一行开始点的id, start. 和最后点的id, end. 这一行的最大宽度就是end-start+1.
Time Complexity: O(n).
Space: O(n).
AC Java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 public int widthOfBinaryTree(TreeNode root) { 12 if(root == null){ 13 return 0; 14 } 15 16 LinkedList<Pair> que = new LinkedList<Pair>(); 17 que.add(new Pair(root,1)); 18 int curCount = 1; 19 int nextCount = 0; 20 21 int res = 1; 22 int start = 1; 23 int end = start; 24 25 while(!que.isEmpty()){ 26 Pair cur = que.poll(); 27 curCount--; 28 end = cur.id; 29 30 if(cur.node.left != null){ 31 que.add(new Pair(cur.node.left, cur.id*2)); 32 nextCount++; 33 } 34 35 if(cur.node.right != null){ 36 que.add(new Pair(cur.node.right, cur.id*2+1)); 37 nextCount++; 38 } 39 40 if(curCount == 0){ 41 res = Math.max(res, end-start+1); 42 curCount = nextCount; 43 nextCount = 0; 44 start = que.isEmpty() ? 1 : que.peek().id; 45 end = start; 46 } 47 } 48 49 return res; 50 } 51 } 52 53 class Pair{ 54 TreeNode node; 55 int id; 56 public Pair(TreeNode node, int id){ 57 this.node = node; 58 this.id = id; 59 } 60 }
类似Binary Tree Level Order Traversal.
LeetCode 662. Maximum Width of Binary Tree
原文：https://www.cnblogs.com/Dylan-Java-NYC/p/10982764.html