题目描述

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

注意:

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

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

时间&空间复杂度

• 时间复杂度： O(nlogn)
• 空间复杂度：O(n)

参考文献

GO 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    lenp, leni := len(preorder), len(inorder)
    if lenp != leni || lenp == 0 {
        return nil 
    }

    return dfs(preorder, 0, lenp-1, inorder, 0, leni-1)
}

func dfs(preorder []int, pStart int, pEnd int, inorder []int, iStart int, iEnd int) *TreeNode{
    if pStart > pEnd || iStart > iEnd {
        return nil 
    }
    rootVal := preorder[pStart]
    var nodeIndex int
    for i,v := range inorder{
        if v == rootVal{
            nodeIndex = i
            break
        }
    }

    leftLength := nodeIndex -iStart

    left := dfs(preorder, pStart+1, pStart+leftLength, inorder, iStart, nodeIndex-1)
    right := dfs(preorder, pStart+leftLength+1, pEnd, inorder, nodeIndex+1,iEnd)

    return &TreeNode{Val:rootVal, Left:left, Right:right}
}