剑指提供程序设计问题-二叉搜索树的后遍历序列

标题说明

输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

思考:

首先，此问题的测试点之一: 二分搜索树的特征.

二叉搜索树（也称为二叉排序树）是空树或具有以下属性的二叉树:

1）如果其左子树不为空，则左子树的所有节点上的值都小于根节点的值;

2）如果其右子树不为空二叉排序树的遍历，则右子树的所有节点上的值都大于根节点的值；

3）它的左右子树也是二进制排序树；

解决方案思想1: 如果给定序列是二叉搜索树的后遍历序列，则序列的最后一个元素是二叉搜索树的根节点. 解决该问题的步骤如下:

1）找到根. 给定序列的最后一个元素；

2）反转遍历序列以查于根的第一个元素，然后该元素左侧（包括该元素）的序列为二分搜索树左子树的后遍历序列，并且元素右边（根之外）的顺序为二分搜索树右边子树的后遍历顺序；

3）顺序遍历2）找到的左子树的后遍历序列，如果找到的元素大于根，则返回false；

4）对于2）中划分的左子序列和右子序列，确定它们是否属于二叉搜索树的后遍历序列，即，递归上述步骤1-3.

递归实施代码:

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()<=0){
            return false;
        }
        else if(sequence.size()<3){
            return true;
        }
        int root=sequence[sequence.size()-1];
        int i=sequence.size()-2;
        while(sequence[i]>=root && i>=0){
            --i;
        }
        if(i>=0 && i<sequence.size()-2){
            int j=0;
            while(j<=i){
                if(sequence[j]>root){
                    return false;
                }
                ++j;
            }
            vector<int> left(sequence.begin(),sequence.begin()+i+1);
            vector<int> right(sequence.begin()+i+1,sequence.end()-1);
            return VerifySquenceOfBST(left)&&VerifySquenceOfBST(right);
        }
        else{
            vector<int> child(sequence.begin(),sequence.end()-1);
            return VerifySquenceOfBST(child);
        }
    }
};

非递归实施思路:

非递归也基于递归的思想. 左子树中所有节点的值小于根节点的值且小于右子树中所有节点的值. 根节点将被删除二叉排序树的遍历，其余序列分为左右两部分. 右子序列的最后一位是右子树的根，它也大于左右子序列的所有值. 子树处理.

问题代码:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-220875-1.html