java - 一棵树的左 View 或右 View

提供树的左/右视图的有效代码是什么。
例如：

                                1
                              /   \
     left view--->>          4     7                    <<--right view
                            / \   /
                           3   2  9
                                 /
                                8

此树的左视图为-1 4 3 8，右视图为-1 7 9 8
我试过水平顺序遍历，但是如果树上缺少一些子节点，那么我很难找到水平的起点（在左视图的情况下）或终点（在右视图的情况下），请给出建议

最佳答案

你说得对，水平顺序遍历

Queue<Node> queue = new ArrayDeque<Node>();
for (Node node = root; node != null; node = queue.poll()) {
    if (node.leftChild != null) queue.add(node.leftChild);
    if (node.rightChild != null) queue.add(node.rightChild);
}

很难知道一个层次的结束和下一个层次的开始。这可以通过使用两个队列来解决。

Queue<Node> currentLevel = new ArrayDeque<Node>();
if (root != null) currentLevel.add(root);
while (true) {
    Node node = currentLevel.poll();
    if (node == null) break;
    /* node is the leftmost on its level */
    Queue<Node> nextLevel = new ArrayDeque<Node>();
    do {
        if (node.leftChild != null) nextLevel.add(node.leftChild);
        if (node.rightChild != null) nextLevel.add(node.rightChild);
        node = currentLevel.poll();
    } while (node != null);
    currentLevel = nextLevel;
}