题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
第一想法
- 什么是二叉搜索树
- 二叉树的后序遍历不能确定该树
二叉搜索树定义
二叉搜索树：又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树
1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3、它的左右子树也分别为二叉搜索树
中序序列{0,1,2,3,4,5,6,7,8,9} 是一个递增序列
先序序列{5,3,1,0,2,4,7,6,8,9}
后序序列{0,2,1,4,3,6,9,8,7,5}
我发现后续遍历就是从左下开始的层序遍历
- 0
- 2 1
- 4 3
...
我看见说本题知识点有栈,可不可以从这个方面去考虑
看了讨论区
就很简单的去尾依据是否大于尾元素分为前后两部分。
那么重建二叉树，输出中序序列？但是题目并没有给出树结点的结构体。是否还有别的判断方法？
依据二叉搜索树的定义判断。
- 左右子树也分别为二叉搜索树
有个问题
- 如上所示,其后序遍历结果是{0,1,2}但是并不是二叉搜索树,估通过后序序列并不能还原二叉搜索树.但是,{0,1,2}确实是二叉搜索树b的后序遍历结果.
思路
1.最后的一个数为r(root)
2.找到第一个大于r的数,其后如果有小于r的,就不是二叉搜索树.
3.递归寻找子树.
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size() == 0) return false;
else
return judge(sequence);
}
bool judge(vector<int> sequence){
if(sequence.size() == 0) return true;
if(sequence.size() > 2){
vector<int> seqleft, seqright;
bool flag = true;
int rear = sequence.size() - 1;
for(int i = 0;i < sequence.size() - 1;i++){
if(sequence[i] > sequence[rear]){
flag = false;
seqright.push_back(sequence[i]);
}
if(flag)
seqleft.push_back(sequence[i]);
}
if(seqright.size() + seqleft.size() != sequence.size() - 1)
return false;
return judge(seqleft) && judge(seqright);
}
else
return true;
}
};
具体做法
- 在sequence中找到最后一个值r
- 找到第一个大于r的数,将此前的数全部push进left.将大于r的数push进right
- 通过判断right的push是不是完全来判断是否是二叉搜索树(因为右边序列可能有小于r的,这样这棵就不是二叉搜索树了,push进去的数量会变少.
left.size()+right.size() != seq.size() - 1减1是把rear尾数提出来的缘故)
又用三个参数的写了一遍
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size() == 0) return false;
else
return judge(sequence, 0, sequence.size() - 1);
}
bool judge(vector<int>& seq, int begin, int end){
if(begin >= end) return true;
int mid = begin;
while(seq[mid] < seq[end] && mid < end){
mid++;
}
for(int j = mid; j < end;j++){
if(seq[j] < seq[end])
return false;
}
return judge(seq, begin, mid - 1) && judge(seq, mid, end - 1);
}
};
发现一个规律
for(){
if(){
break;
}
}
这样的代码可以用while()简写
int mid;
for(int i = begin;i < end;i++){
if(seq[i] > seq[end]){
mid = i;
break;
}
}
int mid = begin;
while(seq[mid] < seq[end] && mid < end){
mid++;
}
