二叉树的最大宽度 - Java代码

Question

下面是问题：

给定一个二叉树，写一个函数来获得给定树的最大宽度。树的宽度是所有级别中的最大宽度。二叉树与完整的二叉树具有相同的结构，但有些节点为空。

一个级别的宽度定义为终端节点之间的长度（级别中最左边和最右边的非空节点，其中终端节点之间的空节点也计入长度计算中。

这里是我的代码：

public class MaxWidth { 
    public int widthOfBinaryTree(TreeNode root) { 
     Queue<TreeNode> queue = new LinkedList<>(); 
     queue.offer(root); 
     int maxWidth = queue.size(); 

     while (! queue.isEmpty()) { 
      int size = queue.size(); 
      for (int i = 0; i < size; i++) { 
       TreeNode rootCur = queue.poll(); 
       if (rootCur.left != null) { 
        queue.offer(root.left); 
       } 
       if (rootCur.right != null) { 
        queue.offer(root.right); 
       } 
      } 

      if (queue.size() > maxWidth) { 
       maxWidth = queue.size(); 
      } 
     } 

     return maxWidth; 
    } 
} 

然而，这结束了一个无限循环〜我也不知道为什么感谢

补充：？！输入树结构是：

   1 
      3  2 
     5 3  9 

Answer 1

if (rootCur.left != null) { 
    queue.offer(root.left); ==> Change root to rootCur 
} 
if (rootCur.right != null) { 
    queue.offer(root.right); ==> Change root to rootCur 
} 

您正在添加root.left和root.right中的元素，因此队列永远不会被耗尽。

Answer 2

的问题是在这里：

if (rootCur.left != null) { 
    queue.offer(root.left); // this is not rootCur! 
} 
if (rootCur.right != null) { 
    queue.offer(root.right); // this is not rootCur! 
}