问题描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000
解题思路
对于二叉搜索树来说，任意结点的左子树中的所有结点值都小于等于该结点的值，右子树中的所有结点的值都大于该结点的值。
对于后序遍历来说，最后遍历到的结点一定是树的根结点。
所以可以将后序遍历的最后一个结点作为二叉搜索树的根结点，该结点的值将数组分成了两部分，前面一部分的值都小于等于该结点，后面一部分的值都大于该结点。
然后递归检验左右子树是否满足条件即可。
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(left: int, right: int) -> bool:
if left >= right: return True
i, mid = left, left - 1
while i < right and postorder[i] < postorder[right]:
mid = i
i += 1
while i < right and postorder[i] > postorder[right]:
i += 1
return i == right and dfs(left, mid) and dfs(mid + 1, right - 1)
return dfs(0, len(postorder) - 1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
bool dfs(vector<int> &postorder, int left, int right) {
if (left >= right) return true;
int i = left, mid = left - 1;
while (i < right && postorder[i] < postorder[right]) mid = i, ++i;
while (i < right && postorder[i] > postorder[right]) ++i;
return i == right && dfs(postorder, left, mid) && dfs(postorder, mid + 1, right - 1);
}
bool verifyPostorder(vector<int>& postorder) {
return dfs(postorder, 0, postorder.size() - 1);
}
};
|