LeetCode-106.从中序与后序遍历序列构造二叉树

二叉树#

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

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

示例 2:

1
输入：inorder = [-1], postorder = [-1]
2
输出：[-1]

看思路后的解法

思路：与 105. 从前序与中序遍历序列构造二叉树 类似，只是储存root的顺序不一样，一个是中左右，一个是左右中

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(inorder []int, postorder []int) *TreeNode {
10
    if len(inorder) == 0 {
11
        return nil
12
    }
13

14
    nodeVal := postorder[len(postorder)-1]
15
    node := &TreeNode{Val: nodeVal}
16

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

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

28
    size := len(leftinorder)
29
    leftpostorder := postorder[:size]
30
    rightpostorder := postorder[size:len(postorder)-1]
31

32
    node.Left = buildTree(leftinorder, leftpostorder)
33
    node.Right = buildTree(rightinorder, rightpostorder)
34

35
    return node
36
}