错误的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。