题目描述

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

二叉树中每个节点的值都互不相同；
输入的前序遍历和中序遍历一定合法；

直接上go的，思想和其他的一致

算法1

go 代码

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

//为中序创建一个map，因为中序需要记住根节点位置，前序不需要
var inmap = make(map[int]int)

func buildTree(preorder []int, inorder []int) *TreeNode {
    for i,in := range inorder {
        inmap[in] = i
    }
    return dfs(preorder,inorder,0,len(inorder)-1,0,len(inorder)-1)
}

//pl：前序树的左边界，pr前序树的右边界，il：中序树的左边界，ir中序树的右边界
func dfs(preorder []int, inorder []int, pl int, pr int, il int ,ir int) *TreeNode {
    var root *TreeNode = new(TreeNode)
    //左边界大于右边界，子树为空
    if il > ir {
        return nil
    }
    root.Val = preorder[pl]

    //左子树长度
    ll := inmap[root.Val] - il

    root.Left = dfs(preorder , inorder , pl + 1 , pl + ll , il , inmap[root.Val]-1 )
    root.Right = dfs(preorder , inorder , pl + ll + 1 , pr , inmap[root.Val] + 1 , ir )

    return root
}