899006a1bdcdb9378dee68c5875bbd43
(难度Medium) Problem 105. Construct Binary Tree from Preorder and Inorder Traversal(先序中序构建二叉树)

Construct Binary Tree from Preorder and Inorder Traversal

Difficulty

Medium

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

题意

给定一棵二叉树的先序遍历以及中序遍历的结果,要求生成二叉树。

题解

题意不难,对于中序遍历很多同学相比非常熟悉了,我们之前接触过好几次。但是先序遍历很多同学没有接触过,有些不太了解,下面,我和大家分享一种非常简单的方法可以一劳永逸地解决问题。

二叉树的遍历顺序一共有三种,分别是先序遍历、中序遍历以及后序遍历。

这三者的差别只有一个地方,就是父亲节点的遍历位置。我们用中表示父亲节点,左表示左儿子,右表示右儿子。那么先序遍历就是中左右,中序遍历时左中右,后序就是左右中。也就是说中在前面就是先序,在中间就是中序,在后面就是后序。

这道题当中我们有了先序和中序,该怎么入手呢?

我们先观察一下,很容易得出结论,既然有了先序,那么第一个遍历的元素就是树根。然后是左子树,最后是右子树。在中序遍历当中呢?应该先是左子树,然后是树根,最后是右子树。

如果没有中序遍历的结果,我们是不知道左子树和右子树的划分位置的。但是有了中序遍历之后,我们就解决了这个问题。因为我们已经知道树根了,所以只需要判断一下树根出现的位置,左边就是左子树,右边是右子树。

这个性质并不是只在树根成立,而是可以递归的。也就是说我们对于每个子树都如此操作,就可以生成出完整的二叉搜索树了。

附上代码:

```C++
class Solution {
public:
TreeNode* dfs(vector& preorder, vector& inorder) {
if (preorder.size() == 0) return nullptr;
// 对于每课子树而言,先序当中0的位置都是根节点

top Created with Sketch.