从有序遍历和级别遍历构造二叉树 [英] Construct binary tree from inorder and level traversal

问题描述

在顺序和级别遍历的情况下，需要帮助找到一种构造二叉树的方法.因为必须通过使用队列来进行级别遍历，所以可以使用递归来做到这一点吗?

Need help finding a way to construct a binary tree given the inorder and level traversal. Is it possible to do it using recursion since the level traversal has to be done by using a queue?

推荐答案

这是解决此问题的方法.通过反向查看，更容易想到如何执行每个步骤:

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

您具有以下条件:

顺序:1 2 4 6 8 9 10

级别:8 4 9 2 6 10 1

级别遍历是树的从左到右，从上到下的遍历(如广度优先搜索).在此示例中，您知道8将是根节点.现在查看顺序遍历，我们知道1 2 4 6组成了左子树，而9 10组成了右子树.因此，我们有:

A level traversal is a left to right, top to down traversal of the tree (like breadth-first search). In this example, you know that 8 will be the root node. Now looking at the inorder traversal, we know that 1 2 4 6 make up the left subtree and 9 10 make the right subtree. So we have:

        8
1 2 4 6   9 10

在保留顺序的同时，创建级别遍历的副本，而无需进行左右递归构造要访问的节点.下面的音符将通过左边的树步骤以及传递的内容:

While preserving order, create a copy of the level traversal without the nodes we are going to visit for the left and right recursive construction. Below notes will go through the left tree steps and what is passed through:

顺序:1 2 4 6

级别:4 2 6 1

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

• Root: 4
• Left subtree: 1 2
• Right subtree: 6

结果:

        8
       /  9 10
      4
  2 1  \
        6

3级-左子树

顺序:1 2

级别:2 1

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

• Root: 2
• Left subtree: 1
• Right subtree: empty

结果:

       8
      /  9 10
     4
    / \   
   2   6
  /
 1

现在我们已经完成了从左到右的递归操作，希望您能逐步了解如何与树的正确子对象打交道！一旦有了算法，您就应该能够通过两次不同的遍历构造回树.关键是要基于两次遍历来识别如何在每次递归调用时确定 root ，其余的应该继续进行.

Now that we're done recursing all the way left, hopefully you can walk through on how to deal with the right children of the tree! Once you have the algorithm, you should be able to construct back the tree given two different traversals. The key is to recognize based on the two traversals how to determine the root at each recursive call, and the rest should follow through.

这篇关于从有序遍历和级别遍历构造二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！