二叉搜索树Binary Search Tree

题目描述

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

第一想法

什么是二叉搜索树
二叉树的后序遍历不能确定该树

二叉搜索树定义

二叉搜索树：又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树

1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3、它的左右子树也分别为二叉搜索树

中序序列{0,1,2,3,4,5,6,7,8,9} 是一个递增序列
先序序列{5,3,1,0,2,4,7,6,8,9}
后序序列{0,2,1,4,3,6,9,8,7,5}

我发现后续遍历就是从左下开始的层序遍历

0
2 1
4 3
...

我看见说本题知识点有栈,可不可以从这个方面去考虑

看了讨论区

就很简单的去尾依据是否大于尾元素分为前后两部分。

那么重建二叉树，输出中序序列？但是题目并没有给出树结点的结构体。是否还有别的判断方法？
依据二叉搜索树的定义判断。

左右子树也分别为二叉搜索树

有个问题

如上所示,其后序遍历结果是{0,1,2}但是并不是二叉搜索树,估通过后序序列并不能还原二叉搜索树.但是,{0,1,2}确实是二叉搜索树b的后序遍历结果.

思路

1.最后的一个数为r(root)
2.找到第一个大于r的数,其后如果有小于r的,就不是二叉搜索树.
3.递归寻找子树.

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) return false;
        else
            return judge(sequence);
    }
    bool judge(vector<int> sequence){
        if(sequence.size() == 0) return true;
        if(sequence.size() > 2){
            vector<int> seqleft, seqright;
            bool flag = true;
            int rear = sequence.size() - 1;
            for(int i = 0;i < sequence.size() - 1;i++){
                if(sequence[i] > sequence[rear]){
                    flag = false;
                    seqright.push_back(sequence[i]);
                }
                if(flag)
                    seqleft.push_back(sequence[i]);
            }
            if(seqright.size() + seqleft.size() != sequence.size() - 1)
                return false;
            return judge(seqleft) && judge(seqright);
        }
        else
            return true;
    }
};

具体做法

在sequence中找到最后一个值r
找到第一个大于r的数,将此前的数全部push进left.将大于r的数push进right
通过判断right的push是不是完全来判断是否是二叉搜索树(因为右边序列可能有小于r的,这样这棵就不是二叉搜索树了,push进去的数量会变少.left.size()+right.size() != seq.size() - 1减1是把rear尾数提出来的缘故)

又用三个参数的写了一遍

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) return false;
        else
            return judge(sequence, 0, sequence.size() - 1);
    }
    bool judge(vector<int>& seq, int begin, int end){
        if(begin >= end)    return true;
        int mid = begin;
        while(seq[mid] < seq[end] && mid < end){
            mid++;
        }
        for(int j = mid; j < end;j++){
            if(seq[j] < seq[end])
                return false;
        }
        return judge(seq, begin, mid - 1) && judge(seq, mid, end - 1);
    }
};

发现一个规律

for(){
  if(){
    break;
  }
}

这样的代码可以用while()简写

int mid;
for(int i = begin;i < end;i++){
    if(seq[i] > seq[end]){
        mid = i;
        break;
    }
}

int mid = begin;
 while(seq[mid] < seq[end] && mid < end){
      mid++;
}