gold-4-5

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
  根节点的值为 5 ，但是其右子节点值为 4 。

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<TreeNode, Integer> maxMap = new HashMap<>();
    private Map<TreeNode, Integer> minMap = new HashMap<>();

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

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

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

        if (root.left != null && root.val <= getTreeMax(root.left)) {
            return false;
        }

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

    private int getTreeMax(TreeNode node) {
        if (node == null) {
            return Integer.MIN_VALUE;
        }
        if (maxMap.containsKey(node)) {
            return maxMap.get(node);
        }

        int leftMax = getTreeMax(node.left);
        int rightMax = getTreeMax(node.right);

        int curMax = Math.max(node.val, Math.max(leftMax, rightMax));
        maxMap.put(node, curMax);

        return curMax;
    }

    private int getTreeMin(TreeNode node) {
        if (node == null) {
            return Integer.MAX_VALUE;
        }
        if (minMap.containsKey(node)) {
            return minMap.get(node);
        }

        int leftMin = getTreeMin(node.left);
        int rightMin = getTreeMin(node.right);

        int curMin = Math.min(node.val, Math.min(leftMin, rightMin));
        minMap.put(node, curMin);

        return curMin;
    }
}
//leetcode submit region end(Prohibit modification and deletion)