题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
1 思考
- 递归出口，递归&& ？？
- 分治法的参数容易出错，永远递归完不了，穿错边界的话
- 还有参数是否引用 影响性能
调试过程
内存不够
超时，因为递归边界不对
容易出错的点汇总
2 代码
第一个是典型的序列倒叙分析， 第二个利用出栈序列的方法，非常的难，为何就可以拉，待思考
//递归出口，递归&& ？？
//分治法的参数容易出错，永远递归完不了，穿错边界的话
//还有参数是否引用 影响性能
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
//if(sequence == NULL){
if(sequence.size() == 0){
return false;//boudary
}
return checkPostTree(sequence, 0 , sequence.size() - 1 ) ;
}
bool checkPostTree(vector<int> sequence, int left , int right){
//tree only 1 node
if(left>=right)
return true;//递归的出口吧
//get root from rihgtest
int root = sequence[right];
//find 分界线对于左边的集合
int j = right - 1;
while( j>=0 && sequence[j]>root){
j--;
}
//左边小的集合看看是否有不合群的，如果有bool,
int i = left;
while( i <=j){
if( sequence[i++] > root){
return false;
}
}
//【】分治法，再分别查左右 两个集合；
// 逻辑容易出错
// // 逻辑容易出错
return checkPostTree(sequence, left , j) && checkPostTree(sequence, j+1 , right);
}
};
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty()) return false;
vector<int> inorder(sequence);
sort(inorder.begin(), inorder.end());
return IsPopOrder(inorder, sequence);
}
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
int n = pushV.size();
stack<int> stk; // 使用STL中的栈容器
int i = 0, j = 0;
while(i < n){
stk.push(pushV[i]); // 首先将pushV[i]入栈
while(!stk.empty() && stk.top() == popV[j]){ // 不断检查栈顶
++j;
stk.pop();
}
++i;
}
return j == n; // 判断能否成功对应
}
};
//https://blog.nowcoder.net/n/237f3c63e3ea4d68949ced0a69e337ab
print('Hello world!')