题目logo-dark-cn.c42314a8.svg

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7

三种遍历方式

前序：又称先序，输出 /输入顺序是先输出根结点的数据，再访问该结点的左子树以及右子树。

中序：输出 /输入顺序是左子树->根结点->右子树

后序：输出 /输入顺序是左子树->右子树->根结点

解题方案：递归

观察题目，可知前序遍历的第一个元素是根节点，由前序遍历的根节点在中序遍历中的位置，可以确定左右子树，在根节点元素左端的是左子树、右端的是右子树

  • 前序遍历的首个元素即为根节点 root 的值；
  • 在中序遍历中搜索根节点 root 的索引 ，可将中序遍历划分为[ 左子树 | 根节点 | 右子树 ] 。
  • 根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ]。

思路：

  1. 设置递归终止条件，如果子树的前序遍历为空，说明根节点不存在，就返回空指针nil
  2. 生成根节点，根节点的数据域就是前序遍历的首元素
  3. 找到根节点在中序遍历中的下标
  4. 根节点位置递归进入左子树
  5. 根节点位置递归进入右子树
  6. 返回根节点 ```go //定义节点结构体 type TreeNode struct { Val int //数据域 Left *TreeNode // 左孩子
    1. Right *TreeNode // 右孩子
    }

// 根据前序遍历和中序遍历复原二叉树 func buildTree(preorder []int, inorder []int) *TreeNode { // 设置递归终止条件，如果子树的前序遍历为空，说明根节点不存在，就返回空指针nil if len(preorder) == 0 { return nil } //根节点存在，则建立根节点 root := &TreeNode{Val : preorder[0]}

//找到根节点在中序遍历中的下标
index := 0
for i := range inorder {
    //找到根节点的位置，保存此时的下标，退出循环break
    if root.Val == inorder[i] {
        index = i
        break
    }
}
 //根节点位置递归进入左子树 
root.Left = buildTree(preorder[1:index+1],inorder[:index])
//根节点位置递归进入右子树 
root.Right = buildTree(preorder[index+1:],inorder[index+1:])

//返回根节点
return root

} ```