面试题07-medium. 重建二叉树

面试题07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

主要思路：

• 为中序遍历建立map映射
• 利用中序遍历和前序遍历规律对中序遍历数组进行分割，划分为不同的“子数组”进行递归操作

注意：公共变量的初始化写法

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 公共变量
var dict map[int]int   // 中序遍历映射字典
var preorderGlobal []int  // 全局前序遍历

// 主函数
func buildTree(preorder []int, inorder []int) *TreeNode {
    preorderGlobal = preorder
    dict =map[int]int{}
    for index,item := range inorder{
        dict[item] = index
    }
    return helper(0,0,len(inorder)-1)
}

// 递归函数 三个参数：前序遍历中root节点的下标，中序遍历左边界，中序遍历右边界
func helper(preRootIndex,inLeftIndex,InRightIndex int) *TreeNode{
      // 递归出口
    if inLeftIndex>InRightIndex{
        return nil
    }
      // 获取root节点在中序遍历中的下标位置
    inRootIndex := dict[preorderGlobal[preRootIndex]]
    root:= TreeNode{
        Val: preorderGlobal[preRootIndex],
        Left:helper(preRootIndex+1,inLeftIndex,inRootIndex-1), // 左子树构建
        Right:helper(preRootIndex+(inRootIndex-inLeftIndex+1),inRootIndex+1,InRightIndex), // 右子树构建：rootindex = 前序遍历root节点下标+左子树长度
    }
    return &root
}