脚本宝典收集整理的这篇文章主要介绍了验证二叉搜索树中的前序序列——lintcode1307，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

验证二叉搜索树中的前序序列

题目：验证二叉搜索树中的前序序列

给定一组数字，验证它是否是二叉搜索树的正确的前序遍历序列。

示例1：

输入: PReorder = [1,3,2]
输出: true

示例2：

输入：preorder=[4,2,1,3,6,5,7]
输出：true

题解

方法1：分治法

public class Solution {
    private int[] order;
    public boolean DFs(int left, int right, int min, int max)
    {
        if(left>right) return true;
        for(int i=left;i<=right;i++)
        {
            if(order[i]>;max || order[i]<min) return false;
        }
        int i;
        for(i=left+1;i<=right;i++)
        {
            if(order[i]>order[left]){
                break;
            }
        }
        return dfs(left+1, i-1, min, order[left])&&dfs(i, right, order[left], max);

    }
    public boolean verifyPreorder(int[] preorder) {
        order=preorder;
        int i;
        for(i=1;i<order.length;i++)
        {
            if(order[i]>order[0]){
                break;
            }
        }
        return dfs(1, i-1, Integer.MIN_VALUE, order[0])&amp;& dfs(i, order.length-1, order[0], Integer.MAX_VALUE);
    }
}

方法2：

左子树：小于根节点

右子树：大于根节点

利用栈，寻找当前节点的根节点

public class Solution1 {

    public boolean verifyPreorder(int[] preorder) {
        int min=Integer.MIN_VALUE;
        Stack<Integer> stack=new Stack<>();
        for (int p : preorder) {
            if(p< min) return false;
            while (!stack.empty() && p>stack.PEek())
            {
                min=stack.pop();
            }
            stack.push(p);
        }
        return true;
    }
}

脚本宝典总结

以上是脚本宝典为你收集整理的验证二叉搜索树中的前序序列——lintcode1307全部内容，希望文章能够帮你解决验证二叉搜索树中的前序序列——lintcode1307所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。