欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的后序遍历序列

程序员文章站 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;
    }
};