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

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

程序员文章站 2022-03-03 09:34:17
...

思路

二叉树中序遍历的结果是依次升序的,则该二叉树是搜索二叉树,否则不是。可在非递归的二叉树中序遍历中稍加修改。

代码

public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

public static boolean isBST(Node head){
    Stack<Node> stack =new Stack<>();
    if (head == null) return true;
    Node cur=head;
    while (!stack.isEmpty() || cur!=null){
        int pre=Integer.MIN_VALUE;
        //当前节点不为空时入栈,当前节点指针指向左孩子
        if (cur!=null){
            stack.add(cur);
            cur=cur.left;
        }else {
            cur=stack.pop();
            //和前一个数比较
            if (cur.value<pre){
                return false;
            }
            pre=cur.value;
            cur=cur.right;
        }
    }
    return true;
}