leetcode — validate-binary-search-tree

import apple.laf.JRSUIUtils;

/**

 * Source : https://oj.leetcode.com/problems/validate-binary-search-tree/

 *

 *

 *

 * Given a binary tree, determine if it is a valid binary search tree (BST).

 *

 * Assume a BST is defined as follows:

 *

 * The left subtree of a node contains only nodes with keys less than the node's key.

 * The right subtree of a node contains only nodes with keys greater than the node's key.

 * Both the left and right subtrees must also be binary search trees.

 *

 * confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 *

 * OJ's Binary Tree Serialization:

 *

 * The serialization of a binary tree follows a level order traversal, where '#' signifies

 * a path terminator where no node exists below.

 *

 * Here's an example:

 *

 *    1

 *   / \

 *  2   3

 *     /

 *    4

 *     \

 *      5

 *

 * The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

 */

public class ValidateBinarySearchTree {

    public boolean validate (TreeNode root) {

        return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

    }

    /**

     * 先判断根节点是否满足 root.value > min && root.value < max，如果满足，再递归判断左右子树

     *

     * @param root

     * @param min

     * @param max

     * @return

     */

    public boolean isValid (TreeNode root, int min, int max) {

        if (root == null) {

            return true;

        }

        if (root.value > max || root.value < min) {

            return false;

        }

        return isValid(root.leftChild, min, root.value) && isValid(root.rightChild, root.value, max);

    }

    /**

     * 二叉搜索树的中序遍历结果是单调递增的，所以中序遍历的时候当前节点值大于上一个节点的值

     * 注意：这里每次递归会改变lastMax的值，需要保存下来，所以这里需要一个类似指针的变量，不能直接使用Integer等包装类型

     *

     * @param root

     * @param lastMax

     * @return

     */

    public boolean isValidByInorder (TreeNode root, TreeNode lastMax) {

        if (root == null) {

            return true;

        }

        if (!isValidByInorder(root.leftChild, lastMax)) {

            return false;

        }

        if (lastMax.value >= root.value) {

            return false;

        }

        lastMax.value = root.value;

        return isValidByInorder(root.rightChild, lastMax);

    }

    public boolean validate1 (TreeNode root) {

        TreeNode lastMax = new TreeNode(Integer.MIN_VALUE);

        return isValidByInorder(root, lastMax);

    }

    public TreeNode createTree (char[] treeArr) {

        TreeNode[] tree = new TreeNode[treeArr.length];

        for (int i = 0; i < treeArr.length; i++) {

            if (treeArr[i] == '#') {

                tree[i] = null;

                continue;

            }

            tree[i] = new TreeNode(treeArr[i]-'0');

        }

        int pos = 0;

        for (int i = 0; i < treeArr.length && pos < treeArr.length-1; i++) {

            if (tree[i] != null) {

                tree[i].leftChild = tree[++pos];

                if (pos < treeArr.length-1) {

                    tree[i].rightChild = tree[++pos];

                }

            }

        }

        return tree[0];

    }

    private class TreeNode {

        TreeNode leftChild;

        TreeNode rightChild;

        int value;

        public TreeNode(int value) {

            this.value = value;

        }

        public TreeNode() {

        }

    }

    public static void main(String[] args) {

        ValidateBinarySearchTree validateBinarySearchTree = new ValidateBinarySearchTree();

        System.out.println(validateBinarySearchTree.validate(validateBinarySearchTree.createTree(new char[]{'1','2','3','#','#','4','#','#','5'})) + "-------false");

        System.out.println(validateBinarySearchTree.validate(validateBinarySearchTree.createTree(new char[]{'3','1','4'})) + "-------true");

        System.out.println(validateBinarySearchTree.validate(validateBinarySearchTree.createTree(new char[]{'3','2','4','1','#'})) + "-------true");

        System.out.println();

        System.out.println(validateBinarySearchTree.validate1(validateBinarySearchTree.createTree(new char[]{'1','2','3','#','#','4','#','#','5'})) + "-------false");

        System.out.println(validateBinarySearchTree.validate1(validateBinarySearchTree.createTree(new char[]{'3','1','4'})) + "-------true");

        System.out.println(validateBinarySearchTree.validate1(validateBinarySearchTree.createTree(new char[]{'3','2','4','1','#'})) + "-------true");

    }

}
巴特西

leetcode — validate-binary-search-tree

最新文章

热门文章
