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

Question

3

需要帮助找到一种构建二叉树的方法，给定中序遍历和层次遍历。是否可以使用递归来完成，因为层次遍历必须使用队列？

- Lexy Feito

构建和遍历略有不同。你想关注哪一个？ - Makoto

两棵树将会大相径庭。（另外，这不是代码。您尝试过什么？） - Makoto

不，我应该从这些遍历中构建一棵树。因为我想先找到一个策略，所以我还没有尝试过任何代码。 - Lexy Feito

我不是要求代码，只是想知道解决问题的方法。 - Lexy Feito

只是为了澄清问题：您有一个中序遍历和层序遍历的“打印输出”，您需要从中完全重建树吗？这棵树是二叉搜索树吗？显然，您可以将任一遍历中的所有键插入到树中，这将给您一棵树，但不一定是与源树完全相同的树。 - angelatlarge

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Reservedegotist · Accepted Answer

以下是解决这个问题的方法。从反向思考每个步骤可以更容易地确定如何进行：

你有以下内容：

中序遍历：1 2 4 6 8 9 10

层级遍历：8 4 9 2 6 10 1

层级遍历是树的从左到右、从上到下的遍历方式（类似于广度优先搜索）。在这个例子中，我们知道8将成为根节点。现在看中序遍历，我们知道1 2 4 6组成左子树，9 10组成右子树。因此我们有：

        8
1 2 4 6   9 10

保持顺序，复制层遍历的内容，但不包括我们要访问的左右递归构造节点。以下说明将介绍左子树步骤以及通过什么传递：

中序遍历：1 2 4 6

层次遍历：4 2 6 1

结果：

中序遍历: 1 2

层次遍历: 2 1

结果:

现在我们已经完成了所有向左递归的工作，希望你能够了解如何处理树的右子节点！一旦你掌握了算法，就应该能够通过两个不同的遍历构建回树。关键是要根据这两个遍历确定每个递归调用中的根节点，其余部分就可以按照相应的方式进行处理。