题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000
解法
方法一：递归
后序遍历的最后一个元素为根节点，根据二叉搜索树的性质，根节点左边的元素都小于根节点，根节点右边的元素都大于根节点。因此，我们找到第一个大于根节点的位置 $i$，那么 $i$ 右边的元素都应该大于根节点，否则返回 false。然后递归判断左右子树。
时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def dfs(l, r):
if l >= r:
return True
v = postorder[r]
i = l
while i < r and postorder[i] < v:
i += 1
if any(x < v for x in postorder[i:r]):
return False
return dfs(l, i - 1) and dfs(i, r - 1)
return dfs(0, len(postorder) - 1)
|
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 | class Solution {
private int[] postorder;
public boolean verifyPostorder(int[] postorder) {
this.postorder = postorder;
return dfs(0, postorder.length - 1);
}
private boolean dfs(int l, int r) {
if (l >= r) {
return true;
}
int v = postorder[r];
int i = l;
while (i < r && postorder[i] < v) {
++i;
}
for (int j = i; j < r; ++j) {
if (postorder[j] < v) {
return false;
}
}
return dfs(l, i - 1) && dfs(i, r - 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
function<bool(int, int)> dfs = [&](int l, int r) -> bool {
if (l >= r) {
return true;
}
int v = postorder[r];
int i = l;
while (i < r && postorder[i] < v) {
++i;
}
for (int j = i; j < r; ++j) {
if (postorder[j] < v) {
return false;
}
}
return dfs(l, i - 1) && dfs(i, r - 1);
};
return dfs(0, postorder.size() - 1);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func verifyPostorder(postorder []int) bool {
var dfs func(l, r int) bool
dfs = func(l, r int) bool {
if l >= r {
return true
}
v := postorder[r]
i := l
for i < r && postorder[i] < v {
i++
}
for j := i; j < r; j++ {
if postorder[j] < v {
return false
}
}
return dfs(l, i-1) && dfs(i, r-1)
}
return dfs(0, len(postorder)-1)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function verifyPostorder(postorder: number[]): boolean {
const dfs = (l: number, r: number): boolean => {
if (l >= r) {
return true;
}
const v = postorder[r];
let i = l;
while (i < r && postorder[i] < v) {
++i;
}
for (let j = i; j < r; ++j) {
if (postorder[j] < v) {
return false;
}
}
return dfs(l, i - 1) && dfs(i, r - 1);
};
return dfs(0, postorder.length - 1);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | impl Solution {
fn dfs(start: usize, end: usize, max_val: i32, postorder: &Vec<i32>) -> bool {
if start >= end {
return true;
}
let root_val = postorder[end - 1];
for i in (start..end).rev() {
let val = postorder[i];
if val > max_val {
return false;
}
if val < root_val {
return (Self::dfs(start, i, root_val, postorder)
&& Self::dfs(i + 1, end - 1, max_val, postorder));
}
}
Self::dfs(start, end - 1, max_val, postorder)
}
pub fn verify_postorder(postorder: Vec<i32>) -> bool {
Self::dfs(0, postorder.len(), i32::MAX, &postorder)
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | /**
* @param {number[]} postorder
* @return {boolean}
*/
var verifyPostorder = function (postorder) {
const dfs = (l, r) => {
if (l >= r) {
return true;
}
const v = postorder[r];
let i = l;
while (i < r && postorder[i] < v) {
++i;
}
for (let j = i; j < r; ++j) {
if (postorder[j] < v) {
return false;
}
}
return dfs(l, i - 1) && dfs(i, r - 1);
};
return dfs(0, postorder.length - 1);
};
|
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 | public class Solution {
private int[] postorder;
public bool VerifyPostorder(int[] postorder) {
this.postorder = postorder;
return dfs(0, postorder.Length - 1);
}
private bool dfs(int l, int r) {
if (l >= r) {
return true;
}
int v = postorder[r];
int i = l;
while (i < r && postorder[i] < v) {
++i;
}
for (int j = i; j < r; ++j) {
if (postorder[j] < v) {
return false;
}
}
return dfs(l, i - 1) && dfs(i, r - 1);
}
}
|
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 | class Solution {
private var postorder: [Int] = []
func verifyPostorder(_ postorder: [Int]) -> Bool {
self.postorder = postorder
return dfs(0, postorder.count - 1)
}
private func dfs(_ l: Int, _ r: Int) -> Bool {
if l >= r {
return true
}
let rootValue = postorder[r]
var i = l
while i < r && postorder[i] < rootValue {
i += 1
}
for j in i..<r {
if postorder[j] < rootValue {
return false
}
}
return dfs(l, i - 1) && dfs(i, r - 1)
}
}
|
方法二：单调栈
后序遍历的顺序为“左、右、根”，如果我们从右往左遍历数组，那么顺序就变成“根、右、左”，根据二叉搜索树的性质，右子树所有节点值均大于根节点值。
因此，从右往左遍历数组，就是从根节点往右子树走，此时值逐渐变大，直到遇到一个递减的节点，此时的节点应该属于左子树节点。我们找到该节点的直接父节点，那么此后其它节点都应该小于该父节点，否则返回 false。然后继续遍历，直到遍历完整个数组。
此过程，我们借助栈来实现，具体步骤如下：
我们首先初始化一个无穷大的父节点值 $mx$，然后初始化一个空栈。
接下来，我们从右往左遍历数组，对于每个遍历到的元素 $x$：
- 如果 $x$ 大于 $mx$，说明当前节点不满足二叉搜索树的性质，返回
false。
- 否则，如果当前栈不为空，且栈顶元素大于 $x$，说明当前节点为左子树节点，我们循环将栈顶元素出栈并赋值给 $mx$，直到栈为空或者栈顶元素小于等于 $x$，然后将 $x$ 入栈。
遍历结束后，返回 true。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。