是否可以使用深度优先遍历在单独的行上打印二叉树的每一层？

Question

我熟悉使用队列在 O(n) 时间内在单独的行中打印每个级别。我想知道是否有任何方法可以使用预序、中序或 post 序遍历来执行此操作。我有以下代码，但我不知道如何处理 depth 参数。我唯一的想法是在遍历树时使用一个链表数组来存储所有节点，消耗 O(n) 额外 space。有没有更好的方法来做到这一点？

class Node {
 int key;
 Node left;
 Node right;

 Node(int value) {
    key = value;
    left = null;
    right = null;
 }
}

public class bst {

 private Node root;

 bst() {
    root = null;
 }

 private void printTreeRec(Node root, int depth) {
    if(root != null) {
        System.out.println(root.key);
        printTreeRec(root.left, depth + 1);
        printTreeRec(root.right, depth + 1);
    }
 }

 void printTree() {
    printTreeRec(root, 0);
 }

 public static void main(String[] Args) {
    bst tree = new bst();

    tree.insert(25);
    tree.insert(15);
    tree.insert(35);
    tree.insert(7);
    tree.insert(18);
    tree.insert(33);
    tree.insert(36);

    tree.printTree();
 }
}

Answer 1

确实不可能使用上述方法，因为它们会 depth-first 也就是说，它们总是朝着一个方向前进，直到到达分支的尽头。

或者至少不是在算法执行时直接在控制台上打印输出。

这不是一个严格的证明，但它应该描述问题：

预购

    System.out.println(root.key);
    printTreeRec(root.left, depth + 1);
    printTreeRec(root.right, depth + 1);

在特定节点，您首先打印当前节点。然后，你向左走，打印那个节点，依此类推。由于您已经向下移动了控制台，并且您不能返回，这种方法将不起作用

顺序

    printTreeRec(root.left, depth + 1);
    System.out.println(root.key);
    printTreeRec(root.right, depth + 1);

在这种情况下，您从根开始，然后向左走。仍然离开，直到没有更多的子节点。然后你打印。但是现在您将上树，您将如何处理控制台行上的焦点？你必须再次前进。在这种情况下也不可能。

后序

    printTreeRec(root.left, depth + 1);
    printTreeRec(root.right, depth + 1);
    System.out.println(root.key);

在这种情况下，您从根开始，然后向左走。直到你可以。当你做不到的时候，你就开始做对了。一直往右走，直到你可以。然后开始打印。但是现在，与上面类似，你将上树，你将如何处理控制台行上的焦点？你必须再次前进。不可能了。

我们如何让它发挥作用？

我们应该作弊，并传递一个级别变量来了解我们在特定时刻所处的级别。填充一个数据结构，如地图，将包含每个级别的节点值，算法完成计算后，打印结果，每行一个级别，使用地图。

Answer 2

您可以在此处参考讨论：Java DFS solution。 Post 为了方便起见，下面的代码。

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        levelHelper(res, root, 0);
        return res;
    }

public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
    if (root == null) return;
    if (height >= res.size()) {
        res.add(new LinkedList<Integer>());
    }
    res.get(height).add(root.val);
    levelHelper(res, root.left, height+1);
    levelHelper(res, root.right, height+1);
}

是否可以使用深度优先遍历在单独的行上打印二叉树的每一层？

Is it possible to print each level of a binary tree on a separate line using depth-first traversal?

java

algorithm

binary-tree

tree-traversal

depth-first-search

预购

顺序

后序