1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// @Title: 从前序与中序遍历序列构造二叉树 (Construct Binary Tree from Preorder and Inorder Traversal)
// @Author: 15816537946@163.com
// @Date: 2020-08-30 16:38:12
// @Runtime: 4 ms
// @Memory: 3.8 MB
/**
 * 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
	}

	res := &TreeNode{
		Val: preorder[0],
	}

	// 只有一个节点，不需要再找左右节点
	if len(preorder) == 1 {
		return res
	}

	idx := indexOf(res.Val, inorder)
	res.Left = buildTree(preorder[1:idx+1], inorder[:idx])
	res.Right = buildTree(preorder[idx+1:], inorder[idx+1:])

	return res
}

func indexOf(val int, in []int) int {
	for i, v := range in {
		if v == val {
			return i
		}
	}
	return 0
}