检查一颗二叉树是否为二叉查找树BST（Java实现）_java判断bst

1. 需求

给一个二叉树的root结点，判断该结点是否是BST。即要判断该树的所有结点是否满足以下性质：所有结点的左孩子都比它小，右孩子都比它大。

2. 思路

遍历所有结点，判断是否满足左小右大的性质即可。

3. 代码实现

3.1 结点

static class Node<T extends Comparable> {
        T value;
        Node left;// 左子树
        Node right;// 右子树

        public Node() {
        }

        public Node(T value) {
            this.value = value;
        }

        public Node(Node left, T value, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.2 递归实现

3.2.1 代码逻辑

判断一个结点的左结点是否比它小，右结点是否比它大，如果均符合要求，那么继续判断左结点的左右结点、右结点的左右结点…直到结点为叶子结点。

3.2.2 代码

    /**
     * 检查一棵树是否为BST 递归实现
     *
     * @param root 树的root结点
     * @return 树是否为BST
     */
    public static boolean isBST(Node root) {
        //当前结点
        Node curr = root;
        //出口
        //如果该结点没有子结点了 -> return ture
        if (curr.left == null && curr.right == null) {
            return true;
        }
        //左右结点都不为null
        if (curr.left != null && curr.right != null) {
            //左结点比当前结点小&&右结点比当前结点大 -> 继续检查下一层结点
            if (curr.value.compareTo(curr.left.value) > 0 && curr.value.compareTo(curr.right.value) < 0) {
                return isBST(curr.left) && isBST(curr.right);
            }
        }
        //仅左节点为null
        if (curr.left == null) {
            if (curr.value.compareTo(curr.right.value) < 0) {
                return isBST(curr.right);
            }
        }
        //仅右结点为null
        if (curr.right == null) {
            if (curr.value.compareTo(curr.left.value) > 0) {
                return isBST(curr.left);
            }
        }
        //不符合要求 -> 返回false
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

3.3 循环实现

3.3.1 代码逻辑

核心逻辑与递归实现一样，但是循环实现过程比递归要复杂一点，需要通过一个栈结构来完成树的遍历。

栈结构遍历树的具体过程如下：

1. 先把root结点push入栈中
2. pop出栈顶的结点，判断该节点是否不为null，不为null就对其左右节点进行判断是否符合BST的要求，不符合就返回false结束方法，符合就把左右节点push入栈，继续循环
3. 循环体会一直循环直到栈中没有结点，即树已经遍历完成

3.3.2 代码

    /**
     * 检查一棵树是否为BST 循环实现
     *
     * @param root 树的root结点
     * @return 树是否为BST
     */
    public static boolean isBST(Node root) {
        //创建一个栈用来遍历树
        Stack<Node> treeStack = new Stack<>();
        //把根节结点压入栈中
        treeStack.push(root);
        //当栈中还有结点时
        while (!treeStack.isEmpty()) {
            //取出栈顶的结点
            Node curr = treeStack.pop();
            //如果结点不为null
            if (curr != null) {
                //如果该结点的左结点不为null，那么进行比较
                if(curr.left!=null){
                    //curr的值应该比左结点大 -> 继续把左结点压入栈中
                    if (curr.value.compareTo(curr.left.value) > 0){
                        treeStack.push(curr.left);
                    } else {
                        //比左结点小 -> 不是BST
                        return false;
                    }
                }
                //右结点同理
                if(curr.right!=null){
                    //curr的值应该比右结点大 -> 继续把右结点压入栈中
                    if (curr.value.compareTo(curr.right.value) < 0){
                        treeStack.push(curr.right);
                    } else {
                        //比右结点小 -> 不是BST
                        return false;
                    }
                }
            }
        }
        //检查完所有结点均符合要求，那么返回ture
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

4. 总结

实际上，递归实现和循环实现的本质是一样的，递归实现使用的JVM的方法栈，循环实现就自己创建了一个栈结构。

key point：

• 通过栈结构来实现循环遍历树