二叉树的后序遍历序列
程序员文章站
2022-05-20 13:52:02
...
题目:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路:
其实这道题和我们经常说的求二叉树的后序遍历序列不一样,大家一定要看清题意再做。二叉搜索树的特点是左子树比根结点小,右子树比根结点大。后序遍历最后一个元素是根结点,根结点左边的元素都比根结点小,根结点右边的元素都比根结点大。
发现一个后序遍历的规律,根结点的左子树中元素都比根结点的小,根结点的右子树都比根结点的大。所以,定义一个变量,先遍历,遇到小于根节点的加1,直到遇到大于根结点的,继续加1,最后比较该变量与size,小的话就返回false。如果相等的话,继续比较。判断其他子树是否为二叉搜索树。
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int size = sequence.size();
if(size == 0)
return false;
while(--size){
int i=0;
while(sequence[i]<sequence[size])
i++;
while(sequence[i]>sequence[size])
i++;
if(i<size)
return false;
}
return true;
}
};