备忘
利用二叉搜索树的性质:根节点左侧的所有节点的值一定小于等于根节点的值,根节点右侧的
所有节点的值一定大于等于根节点的值
以及后序遍历序列的性质:后序遍历序列的末尾存放着树的根节点
此题可关联《剑指offer》07-从先序中序序列重建二叉树
https://www.acwing.com/solution/content/27602/
和 LeetCode 106-从中序后序序列重建二叉树
https://www.acwing.com/solution/content/27620/
C++ 代码
class Solution {
public:
//递归
bool verifyPostorder(vector<int>& postorder) {
if(postorder.empty())return true;
return isBST(postorder, 0, postorder.size() - 1);
}
bool isBST(vector<int>& post, int l, int r){
if(l >= r)return true;//穿过叶子结点返回true
int flag = post[r];//存放根节店的值
int i = l;//从当前序列的左边界开始遍历
for(; i < r; i ++ ){//找到第一个大于根节点值的位置
//将该节点到尾节点之前的区间( [该节点,尾节点),左闭右开)
//视为右子树对应的序列
if(post[i] > flag)
break;
}
for(int j = i + 1; j < r; j ++ ){//检查右子树对应序列中有无小于等于根节点值的节点
//若有则表示该序列不可能为二叉搜索树对应的后序序列
if(post[j] <= flag)
return false;
}
return isBST(post, l, i - 1) && isBST(post, i, r - 1);//递归判断左子树及右子树
}
};