[数据结构与算法]算法与数据结构-搜索二叉树（BST）

什么是搜索二叉树（BST）？

 搜索二叉树:左子树所有节点的值都比父节点的值小，右子树所有节点的值都比父节点的值大

判断二叉树是否为BST

方法1：递归，根据中序遍历进行改编，将中序遍历的打印步骤改为比较当前节点值和左子树最大值的操作
方法2：非递归，可以使用List和Stack
      ①使用List：使用递归/非递归方式将该树中序遍历的序列进行储存，然后判断该序列是否递增
      ②使用Stack：仿照二叉树中序遍历(Stack)的过程，将打印操作改为比较当前节点值和左子树最大值的操作

代码实现：

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

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

    // 方法1：递归
    public static int preValue = Integer.MIN_VALUE;

    public static boolean checkBSTRec(Node head) {
        if (head == null) {
            return true;
        }
        boolean isLeftBST = checkBSTRec(head.left);// 判断当前节点左树是否为搜索二叉树
        // 注意：preValue是全局变量，执行完checkBSTRec后会变化
        // 如果左树不是搜索二叉树
        if (!isLeftBST) {
            return false;
        }

        // 此时的preValue可以理解为左子树的最大值
        if (head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }
        // 执行到这步说明head的左子树为搜索二叉树，并且head的值大于左子树的最大值
        return checkBSTRec(head.right);

    }

    // 方法2：非递归(使用List)
    public static boolean checkBSTnoRecList(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> inOrderList = new LinkedList<>();
        process(head, inOrderList);
        int pre = Integer.MIN_VALUE;
        // 判断该序列是否为递增序列
        for (Node cur : inOrderList) {
            if (cur.value <= pre) {
                return false;
            }
            pre = cur.value;
        }
        return true;
    }

    // 使用List储存二叉树中序遍历的序列(递归方式)
    public static void process(Node node, LinkedList<Node> inOrderList) {
        if (node == null) {
            return;
        }
        process(node.left, inOrderList);
        inOrderList.add(node);
        process(node.right, inOrderList);

    }

    // 方法3：非递归(使用Stack)
    public static boolean checkBSTnoRecStack(Node head) {
        if (head != null) {
            int preValue = Integer.MIN_VALUE;
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                // 找出每个子树左边界，并压入栈中
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    // 依次弹出栈中节点
                    head = stack.pop();
                    // 该步处理和递归中的操作一样
                    if (head.value <= preValue) {
                        return false;
                    } else {
                        preValue = head.value;
                    }
                    head = head.right;
                }
            }
        }
        return true;
    }
}