一、概述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树

    3
   / \
  9  20
    /  \
   15   7

二、解法

这道题和“从中序与后序遍历序列构造二叉树”特别像，思路就不再展开了，实现如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    
    head := new(TreeNode)
    head.Val = preorder[0]
    
    if len(preorder) == 1 {
        return head
    }
    
    // 获取中序遍历的 左右子树
    var (
        inorderLeft []int
        inorderRight []int
    )
    
    var inTopIndex int
    for preorder[0] != inorder[inTopIndex] {
        inTopIndex ++
    }
    
    inorderLeft = inorder[:inTopIndex]
    if inTopIndex < len(inorder) -1 {
        inorderRight = inorder[inTopIndex+1:]
    }
    
    // 获取左子树
    if len(inorderLeft) > 0 {
        preLeft := preorder[1:len(inorderLeft)+1]
        
        head.Left = buildTree(preLeft, inorderLeft)
    }
    
    // 获取右子树
    if len(inorderRight) > 0 {
        preRight := preorder[len(inorderLeft)+1:]
        head.Right = buildTree(preRight, inorderRight)
    }
    
    return head
}