题解 | #二叉搜索树的后序遍历序列#

二叉搜索树的后序遍历序列

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

#include <vector>
class Solution {
  public:
    //思路:虽然我们无法只靠后序遍历的结果就完整地构建出一棵树,但是既然有了二叉搜索树的这一限定条件(题目只说只要这个后序遍历的结果能满足是某一个二叉搜索树的遍历结果就行,也就是说,重点是放在符合二叉搜索树的定义,而不是构建出原本的树上),我们就只用专心于判断是否满足二叉搜索树的定义即可。
    //递归地判断每一棵子树是否满足定义。
    bool solve(int begin, int end, vector<int>& seq) {
        if (begin == end)
            return true;
        int root = seq[end]; //后序遍历的结果中,最后一个被访问到的是根节点。
        int LesserThanRootCount = 0;
        int GreaterThanRootCount = 0;
        int i = 0;
        for (i = end - 1; i >= begin; i--) {
            if (seq[i] > root) {
                GreaterThanRootCount++;
            } else {
                LesserThanRootCount++;
            }
        }
        if (GreaterThanRootCount == 0 || LesserThanRootCount==0) {
            //左右子树一边为全空的情况。在我们上面的判断中,只有全大于root或全小于Root才会出现这种情况,因此这时root树本身肯定算是满足二叉搜索树的定义了,只要去看它的子树是否满足即可。
            return solve(begin, end-1, seq);
        }

        int leftRoot = begin;
        int rightRoot = end - 1; //后序遍历中,根节点分出的左右两棵子树,其中右子树就是紧挨在根节点左边,因此rightRoot就是end-1,而左子树在的位置还得找找。
        //寻找左子树根的位置。找到后我们才能明确出begin~leftRoot是左子树的范围,rightRoot~end-1是右子树的范围。
        i = 0;
        for (i = end - 1; i >= begin; i--) {
            if (seq[i] < root) {
                leftRoot = i;
                break;
            }
        }
        //判断右子树是否满足全部大于root的条件。
        for (i = end - 1; i > leftRoot; i--) {
            if (seq[i] <= root) {
                return false;
            }
        }
        for (i = leftRoot;i>=begin;i--)
        {
            if(seq[i]>=root)
                return false;
        }
        //熬过了重重考验,现在可以认定这棵root树大体上是满足二叉搜索树的定义,但还要检查它的子树是否满足。
        return solve(begin,leftRoot,seq) && solve(leftRoot+1,end-1,seq);
    }

    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())
            return false;
        return solve(0,sequence.size()-1,sequence);
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 13:15
点赞 评论 收藏
分享
06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务