二叉樹的最大寬度 - 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! 
}