首页 > 其他 > 详细

剑指OFFER 二叉搜索树的后序遍历

时间:2020-02-05 23:31:07      阅读:74      评论:0      收藏:0      [点我收藏+]

剑指OFFER 二叉搜索树的后序遍历

题目描述

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

分析

判断是否是二叉搜索树的后序遍历结果,那么得先明白什么是二叉搜索树,还有什么是后序遍历

技术分享图片

这是一颗二叉搜索树,其每个节点都满足 左孩子<父母<右孩子

其后序遍历为

4 7 5 10 12 11 9
[ 小][  大   ][中]

然后小部分/大部分内部也同样满足这样的规律,那么,用递归是最方便的

代码

class Solution {
public:
    
    bool ok = true;
    vector<int> seq;
    
    int check_right(int a,int b,int mid_val)
    {
        while(b>=a && seq[b]>mid_val)
        {
            b--;
        }
        return b;
    }
    
    int check_left(int a,int b,int mid_val)
    {
        while(a<=b && seq[a]<mid_val)
        {
            a++;
        }
        return a;
    }
    
    void recur(int left,int right)
    {
        if(left >= right)return;
        
        int left_bound = check_left(left,right-1,seq[right]);
        int right_bound = check_right(left,right-1,seq[right]);
        
        if(right_bound + 1 != left_bound){
            ok = false;
            return;
        }
        
        recur(left,right_bound);
        recur(left_bound,right-1);
        
    }
    
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0)return false;
        
        seq = move(sequence);
        
        recur(0,seq.size()-1);
        
        return ok;
        
    }
};

剑指OFFER 二叉搜索树的后序遍历

原文:https://www.cnblogs.com/virgildevil/p/12266964.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!