题目

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

注意:

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

例如，给出

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

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

返回如下的二叉树：

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    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
    }

    root := &TreeNode {Val: preorder[0]}
    if len(preorder) == 1 {
        return root
    }

    index := getIndex(inorder, preorder[0])
    root.Left = buildTree(preorder[1:index+1], inorder[:index])
    root.Right = buildTree(preorder[index+1:], inorder[index+1:])
    return root
}

func getIndex(inorder []int, ele int) int {
    for i, in := range inorder {
        if in == ele {
            return i
        }
    }

    return -1
}

原文

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/4/conclusion/16/