欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树——判断一棵树是否是搜索二叉树

程序员文章站 2022-05-16 10:36:08
...

中序遍历是升序即可

使用二叉树遍历的非递归版本更方便判断

采用二叉树的中序遍历的非递归版本,在其中打印的位置用比较大小代替即可

public class IsBSTTree {
    public static boolean isBSTTree(Tree tree){
        if(tree == null) return true;

        Stack<Tree> stack = new Stack<>();
        int preNode = Integer.MIN_VALUE;

        while(!stack.empty() || tree != null){
            if(tree != null){
                stack.push(tree);
                tree = tree.left;
            }else{
                tree = stack.pop();
                if(preNode > tree.val){
                    return false;
                }
                preNode = tree.val;
                tree = tree.right;
            }
        }
        return true;
    }
}