java - 从中序和层次遍历构建二叉树

Question

需要帮助寻找一种方法来构造给定中序和层次遍历的二叉树。层次遍历必须用队列来做，是否可以用递归来做？

Answer 1

以下是解决此问题的方法。从逆向看更容易想到如何处理每一步:

      8
     / \
    4   9
   / \   \
  2   6   10
 /
1

您有以下内容:

顺序:1 2 4 6 8 9 10

级别:8 4 9 2 6 10 1

1 级 - 根

层次遍历是树的从左到右、从上到下的遍历(类似于广度优先搜索)。在此示例中，您知道 8 将是根节点。现在查看中序遍历，我们知道 1 2 4 6 构成左子树，9 10 构成右子树。所以我们有:

        8
1 2 4 6   9 10

在保持顺序的情况下，创建一个层级遍历的副本，不包含我们要访问的节点，用于左右递归构造。下面的注释将通过左侧的树步骤以及通过的内容:

Level 2 - 左子树

顺序:1 2 4 6

级别:4 2 6 1

• 根:4
• 左子树:1 2
• 右子树:6

结果:

        8
       /  9 10
      4
  2 1  \
        6

Level 3 - 左子树

顺序:1 2

级别:2 1

• 根:2
• 左子树:1
• 右子树:空

结果:

       8
      /  9 10
     4
    / \   
   2   6
  /
 1

现在我们已经完成了向左递归，希望您能逐步了解如何处理树的右子节点!一旦你有了算法，你应该能够在给定两种不同的遍历的情况下重新构造树。关键是在两次遍历的基础上认识到每次递归调用时如何确定root，其余的就跟着走。