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

二叉树#

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

1
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
2
输出: [3,9,20,null,null,15,7]

示例 2:

1
输入: preorder = [-1], inorder = [-1]
2
输出: [-1]

看思路后的解法

思路：从前序遍历序列的第一个元素确定根节点，然后在中序遍历序列中找到该根节点的位置，其左侧为左子树的中序序列，右侧为右子树的中序序列。接着根据左子树的节点个数，在前序序列中划分出左子树和右子树的前序序列，最后递归地构建左右子树即可。

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func buildTree(preorder []int, inorder []int) *TreeNode {
10
    if len(preorder) == 0 {
11
        return nil
12
    }
13

14
    rootVal := preorder[0]
15
    root := &TreeNode{Val: rootVal}
16

17
    var rootIndex int
18
    for i, v := range inorder {
19
        if v == rootVal {
20
            rootIndex = i
21
            break
22
        }
23
    }
24

25
    leftinorder := inorder[:rootIndex]
26
    rightinorder := inorder[rootIndex+1:]
27

28
    size := len(leftinorder)
29
    leftpreorder := preorder[1:size+1]
30
    rightpreorder := preorder[size+1:]
31

32
    root.Left = buildTree(leftpreorder, leftinorder)
33
    root.Right = buildTree(rightpreorder, rightinorder)
34

35
    return root
36
}

ai优化版

1
func buildTree(preorder []int, inorder []int) *TreeNode {
2
    if len(preorder) == 0 {
3
        return nil
4
    }
5

6
    rootVal := preorder[0]
7
    root := &TreeNode{Val: rootVal}
8

9
    var rootIndex int
10
    for i, v := range inorder {
11
        if v == rootVal {
12
            rootIndex = i
13
            break
14
        }
15
    }
16

17
    leftSize := len(inorder[:rootIndex])
18

19
    root.Left = buildTree(preorder[1 : 1+leftSize], inorder[:rootIndex])
20

21
    root.Right = buildTree(preorder[1+leftSize:], inorder[rootIndex+1:])
22

23
    return root
24
}