【每日阅读】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;
    }
}

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/2693

发表评论

登录后才能评论
GitHub
分享本页
返回顶部