leetcode 105 . 从前序与中序遍历序列构造二叉树

题解

前序遍历顺序为根左右,中序遍历顺序为左根右,所以可以看出preorder中的每一个数,在inorder中所处位置的左边就是左子树,右边为右子树

示例代码(go)

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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
var node *TreeNode
if len(preorder) == 0 {
return node
}
node = &TreeNode{preorder[0], nil, nil}
left := 0
for i, v := range inorder {
if v == preorder[0] {
left = i
break
}
}
node.Left = buildTree(preorder[1:left+1], inorder[:left])
node.Right = buildTree(preorder[left+1:], inorder[left+1:])
return node
}