二叉搜索树的后序遍历

剑指offer BTree

Created At : 2019-12-26 23:12

Count:328 Views 👀 :

Comment:

二叉搜索树的后序遍历序列
1. 思路分析

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

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

思路分析

二叉排序树特点，左<根<右
序列中没有重复元素
后续遍历顺序：左右根
因此，按照最后一个元素可以将原序列分割成两个具有相同规律的子序列，然后进行大小验证

  
class Solution {
public:

    bool VerifySquenceOfBST(vector<int> sequence) {
        bool ans = false;
        if (sequence.size() > 0){
            ans = subSequence(sequence,0,sequence.size() - 1);
        }
        return ans;
    }
    
private:
    bool subSequence(vector<int> sequence,int start,int end){
        // >= 是一个范围，== 是一个点，可能会导致内存溢出
        if (start >= end) return true; 
        int i = start;
        // 寻找第一个大于根节点的索引
        for (i = start;i < end;++i) {
            if (sequence[i] > sequence[end]) {
                break;
            }
        }
        // i之后的节点的值都大于根节点，
        // 如果小于，则该序列不是二叉搜索树的后续遍历序列
        for(int j = i + 1;j < end;++j) {
            if (sequence[j] < sequence[end]) {
                return false;
            }
        }
        // 递归遍历，判断
        return subSequence(sequence,start,i - 1) && subSequence(sequence,i,end - 1);
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com