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

在保留顺序的同时，创建一个级别遍历的副本，其中不包含我们将要访问的节点以进行左右递归构造。下面的注释将遍历左侧的树步骤以及经过的内容：

级别 2 - 左子树

为了：1 2 4 6

等级：4 2 6 1

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

结果：

        8
       /  9 10
      4
  2 1  \
        6

第 3 级 - 左子树

为了：1 2

等级：2 1

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

结果：

       8
      /  9 10
     4
    / \   
   2   6
  /
 1

现在我们已经完成了向左的递归，希望您可以了解如何处理树的正确孩子！一旦你有了算法，你应该能够在给定两个不同的遍历的情况下重新构造树。关键是根据两次遍历识别如何在每次递归调用时确定根，其余的应该遵循。