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

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

示例 1：

1
2
输入: [1,6,3,2,5]
输出: false

示例 2：

1
2
输入: [1,3,2,6,5]
输出: true

递归分治

逻辑
- 从后向前遍历，寻找第一个小于根节点的元素下标 i（这样可以保证右子树均大于根节点）
- 对左子树正确性进行判断，即从 i 向前进行遍历，若发现大于根节点的值，则判断不是搜索二叉树，返回 false
- 对左右子树递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func verifyPostorder(postorder []int) bool {
	if len(postorder) == 0 {
		return true
	}
	rootVal := postorder[len(postorder)-1]
	var i int
	for i = len(postorder) - 1; i >= 0; i-- {
		// 找到第一个小于rootVal的下标
		if postorder[i] < rootVal {
			break
		}
	}

	for j := i; j >= 0; j-- {
		if postorder[j] > rootVal {
			return false
		}
	}

	return verifyPostorder(postorder[:i+1]) && verifyPostorder(postorder[i+1:len(postorder)-1])
}