剑指offer——面试题24：二叉搜索树的后序遍历序列

Solution1：

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

参考网址：

class Solution {public:    bool VerifySquenceOfBST(vector
   
     sequence) {        return bst(sequence,0,sequence.size()-1);    }    bool bst(vector
    
      &sequence,int begin,int end){ //整型参数为vector下标        if(sequence.empty()||begin>end)            return false;        int root=sequence[end];        int i=begin;        for(;i
     
      root)//i坐标为右子树第一个节点                break;        for(int j=i;j
      
       begin) //若i==begin,则左子树为空，此时左子树为默认的true            left=bst(sequence,begin,i-1);        bool right=true;        if(i

Solution2：

2018年9月1日重做

class Solution {public:    bool VerifySquenceOfBST(vector
   
     sequence) {        return bst(sequence, 0, sequence.size() - 1);    }    bool bst(vector
    
      &sequence, int begin, int end) { //整型参数为vector下标        if (sequence.empty() || begin > end)            return false;        int root = sequence[end]; //根结点        int i = begin;        //找到左右子树的分割点        for (; i < end; ++i)             if(sequence[i] > root) //i坐标为右子树第一个节点                break;        //右子树结点中若比根结点小 直接返回false        for (int j = i; j < end; ++j)            if(sequence[j] < root)                 return false;        bool left = true;        if (i > begin) //若i==begin,则左子树为空，此时左子树为默认的true            left = bst(sequence, begin, i - 1);        bool right = true;        if(i < end - 1) //若i==end-1，则右子树为一个点，此时右子树为默认的true            right = bst(sequence, i, end - 1);        return left&&right;    }};

转载地址：http://dxhdb.baihongyu.com/

你可能感兴趣的文章