确定数组是否是遍历二叉搜索树的结果（思想和实现）(2)

想法3:

已知条件:

后续序列的最后一个值是root. 二叉搜索树的左子树小于根，右子树大于根.

I. 确定根；

第二，遍历序列（不包括根节点），找到比根大的第一个位置二叉排序树 遍历，然后该位置的左侧是左子树，右侧是右子树；

三，遍历右边的子树，如果发现有一个小于根的值，则直接返回false；

第四，确定左和右子树是否仍然是二叉搜索树（即，递归步骤1、2和3）.

代码实现:

class Solution {
public:
    bool VerifySquenceOfBST(vector
<int> sequence) {
        vector
    <int> leftTree,rightTree;
        int root; // 根结点
        if(sequence.empty()) return false;
        int index = 0; // 标记左右子树界限
        int len = sequence.size();
        root = sequence[len-1];
        int i=0;
        for(;i<len-1;++i)
        {
            if(sequence[i]>root) break; // 找到第一个大于根结点的位置，则左边为左子树，右边为右子树
        }
        for(int j=i;j
        <len-1;++j) // 循环时去除root，因此为len-1
        {
            if(sequence[j]
            <root) return false; // 有一个小于root，则返回false
        }
         
        if(i!=0)
        {
            // 即有左子树
            for(int m=0;m
                <i;++m)
            {
                leftTree.push_back(sequence[m]);
            }
        }
        if(i!=len-2)
        {
            for(int j=i;j
                    <len-1;++j)
            {
                rightTree.push_back(sequence[j]);
            }
        }
         
        bool left = true,right = true; // 看左右子树是否是二叉搜索树
        if(leftTree.size()>1) VerifySquenceOfBST(leftTree);
        if(rightTree.size()>1) VerifySquenceOfBST(rightTree);
         
        return (left&&right);
    }
};

您是否了解以上三个想法和代码实现？如果您想了解更多Java示例，请继续学习QiQ Tools Network的Java示例专栏！

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