二叉树方面的验证
实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。
链接：
注：牛客网测试数据集多了对空数据的判断
递归（分治）
#include <climits>
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==0)return false;
return postOrder(sequence, 0, sequence.size()-1);
}
private:
bool postOrder(vector<int>&vec, int i, int j){
if(i>=j)return true;
int p=i;
while(vec[p]<vec[j])p++;
int m=p;
while(vec[p]>vec[j])p++;
bool verify_root = (p==j);
bool verify_left = postOrder(vec, i, m-1);
bool verify_right = postOrder(vec, m, j-1);
return verify_root && verify_left && verify_right;
}
};
迭代（单调栈）
#include <climits>
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==0)return false;
int root=INT_MAX;
stack<int>s;
for(int i=sequence.size()-1;i>=0;i--){//loop for element
if(sequence[i]>root)return false;
//first decrease , find it's root
while(!s.empty() && s.top()>sequence[i]){//loop for stack
root=s.top();
s.pop();
}
s.push(sequence[i]);
}
return true;
}
};
文档信息
- 本文作者：Chaojie Men
- 本文链接：https://menchaojie.github.io/2024/06/29/Verify-Tree-Order/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）