题目链接:剑指 Offer 33. 二叉搜索树的后序遍历序列
方法:分治
解题思路
- 首先假设该序列能够构成某个二叉搜索树的后序遍历序列,那么这个序列会被分成3个部分:左子树序列,右子树序列,父节点,其中左右子树节点数可能为0;
- 现在就可以检查该序列是否符合这个规律,然后递归的判断子树是否符合规律。
- 当序列的大小(即树的大小) \(<= 3\) 时,该序列一定可以构成二叉搜索树的后序遍历序列;
- 从右向左找到第一个小于父节点的值的下标,那么从该下标到序列起点的部分为左子树序列,此时判断左子树序列中是否全部小于父节点的值,一旦有一个不符合则返回false;然后若左右子树存在,则继续检查其对应子树。
代码
class Solution {
public:
bool check(vector<int>& postorder, int l, int r) {
if (r - l <= 2) return true;
int leftchild = r;
bool flag = true;
while (leftchild >= l) { // 从右向左找到第一个小于父节点的值的下标
if (postorder[leftchild] >= postorder[r]) leftchild -- ;
else break;
}
if (leftchild != l - 1) {
int idx = leftchild;
while (idx >= l) { // 一旦有一个 >= root,则返回false
if (postorder[idx] >= postorder[r]) return false;
idx -- ;
}
flag &= check(postorder, l, leftchild); // 检查其对应子树
}
if (leftchild != r - 1) {
flag &= check(postorder, leftchild + 1, r - 1); // 检查其对应子树
}
return flag;
}
bool verifyPostorder(vector<int>& postorder) {
int n = postorder.size();
return check(postorder, 0, n - 1);
}
};
复杂度分析
时间复杂度:\(O(n^2)\),最坏情况退化为链表,每轮遍历当前所有节点;
空间复杂度:\(O(n)\),调用栈空间,最坏情况为高度为n;