バイナリツリーの最大幅 - Javaコード

Question

以下は質問です。

与えられたツリーの最大幅を取得する関数を作成します。ツリーの幅は、すべてのレベルの中で最大の幅です。バイナリツリーは完全なバイナリツリーと同じ構造を持ちますが、いくつかのノードはヌルです。

1つのレベルの幅は、エンドノード間の長さとして定義されます（エンドノード間のヌルノードも長さの計算にカウントされるレベルの最も左と右端の非ヌルノード）。

そして、ここに私のコードです：

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! 
}