剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

根据 BST 的特点，左子树的值都小于根节点，右子树的值都大于根节点。

又根据后序遍历为 “左右根” 的特点，在后序遍历序列中，最末尾元素是根节点。

从左数起，比根节点小的都是左子树，且最后一个是左子树的根。剩下部分就是右子树。验证了 左子树的值都小于根节点，右子树的值都大于根节点 这一条件后，递归验证两颗子树。

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
func verifyPostorder(postorder []int) bool {
    return verify(postorder, 0, len(postorder)-1)
}

func verify(postorder []int, left, right int) bool {
    // 空树是 BST
    if left > right {
        return true
    }
 
    // 根节点是序列最后一个元素
    rootVal := postorder[right]
    leftRootIdx := right-1

    // 从左数起，遇到第一个比根节点大的元素，它前一个元素就是左子树根节点
    for i := left; i < right; i++ {
        if postorder[i] > rootVal {
            leftRootIdx = i-1
            break
        }
    }
    rightRootIdx := right - 1

    // 验证右子树是否都大于根节点
    for i := leftRootIdx + 1; i <= rightRootIdx; i++ {
        if postorder[i] < rootVal {
            return false
        }
    }

    // 递归验证左右子树是否为 BST
    return verify(postorder, left, leftRootIdx) && verify(postorder, leftRootIdx+1, rightRootIdx)
}