錯誤的LevelOrder遍歷

Question

如何修復這個LevelOrder遍歷？

public static void LevelOrder(TreeNode root){ 
     Queue <TreeNode> q = new LinkedList <>(); 
     TreeNode tmp=root; 
     q.add(tmp); 
     while (!q.isEmpty()) { 
      System.out.print(q.remove().data + " "); 
      if (tmp.left!=null) { 
       q.add(tmp.left); 
      } 
      if (tmp.left!=null) { 
       q.add(tmp.right); 
      } 
       tmp = q.peek(); 
     } 

    } 

Answer 1

不僅僅是remove()從隊列中不存儲。將它保存在一個變量中，因爲您需要它來檢查左側和右側。你也沒有檢查是否root是null。一個可能的修復這兩個問題：

public static void LevelOrder(TreeNode root) { 
    Queue<TreeNode> q = new LinkedList<>(); 
    q.add(root); 
    while (!q.isEmpty()) { 
     TreeNode tmp = q.remove(); 
     if (tmp == null) { 
      continue; 
     } 
     System.out.print(tmp.data + " "); 
     q.add(tmp.left); 
     q.add(tmp.right); 
    } 
} 

相反的remove()，我建議使用poll()。不同的是，remove()將在隊列爲空時拋出異常。但由於環路條件，我們知道不能發生。有關LinkedList的各種方法的更多詳細信息，請參閱JavaDoc。