错误的层次顺序遍历

Question

我该如何解决这个 Level Order 遍历问题？

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);
    }
}

我建议使用 poll() 而不是 remove()。不同的是remove()如果队列为空会抛出异常。但多亏了循环条件，我们知道这不可能发生。有关 LinkedList 的各种方法的更多详细信息，请参阅 JavaDoc.

错误的层次顺序遍历

Wrong LevelOrder Traversal

java

algorithm

queue

tree

traversal