【每日阅读】2020年11月17日-验证二叉搜索树

思路：中序遍历时，BST是升序的。

package algorithm.tree;

public class BstVerify {
    private static Integer lastNum = null;

    public static void main(String[] args) {
        TreeNode root = getTree();

        System.out.println("是BST: " + midVerify(root));
    }

    /**
     * 使用中序遍历的方式验证是否是BST
     */
    private static boolean midVerify(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!midVerify(root.left)) {
            return false;
        }

        if (lastNum != null && lastNum >= root.val) {
            return false;
        }

        lastNum = root.val;

        if (!midVerify(root.right)) {
            return false;
        }

        return true;
    }

    /**
     *     5
     *    / \
     *   2   6
     *  / \
     * 1   4
     *    /
     *   3
     */
    private static TreeNode getTree() {
        TreeNode root = new TreeNode(5);

        root.setLeft(new TreeNode(2));
        root.setRight(new TreeNode(6));

        root.getLeft().setLeft(new TreeNode(1));
        root.getLeft().setRight(new TreeNode(4));

        root.getLeft().getRight().setLeft(new TreeNode(3));

        return root;
    }
}