lc-98

//Given the root of a binary tree, determine if it is a valid binary search tree
// (BST). 
//
// A valid 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 no
//de's key. 
// Both the left and right subtrees must also be binary search trees. 
// 
//
// 
// Example 1: 
//
// 
//Input: root = [2,1,3]
//Output: true
// 
//
// Example 2: 
//
// 
//Input: root = [5,1,4,null,null,3,6]
//Output: false
//Explanation: The root node's value is 5 but its right child's value is 4.
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is in the range [1, 104]. 
// -231 <= Node.val <= 231 - 1 
// 
// Related Topics Tree Depth-First Search Binary Search Tree Binary Tree 
// 👍 11931 👎 978


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


        return isValidBST(root, maxMap, minMap);
    }

    boolean isValidBST(TreeNode node, Map<TreeNode, Integer> maxMap, Map<TreeNode, Integer> minMap) {
        if (node.left != null) {
            int leftMax = getMax(node.left, maxMap);

            if (leftMax >= node.val) {
                return false;
            }

            if (!isValidBST(node.left, maxMap, minMap)) {
                return false;
            }
        }
        if (node.right != null) {
            int rightMin = getMin(node.right, minMap);

            if (rightMin <= node.val) {
                return false;
            }

            if (!isValidBST(node.right, maxMap, minMap)) {
                return false;
            }
        }

        return true;
    }


    int getMax(TreeNode node, Map<TreeNode, Integer> maxMap) {
        if (maxMap.containsKey(node)) {
            maxMap.get(node);
        }

        int leftMax = node.left != null ? getMax(node.left, maxMap) : Integer.MIN_VALUE;
        int rightMax = node.right != null ? getMax(node.right, maxMap) : Integer.MIN_VALUE;

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

        maxMap.put(node, max);
        return max;
    }

    int getMin(TreeNode node, Map<TreeNode, Integer> minMap) {
        if (minMap.containsKey(node)) {
            minMap.get(node);
        }

        int leftMin = node.left != null ? getMin(node.left, minMap) : Integer.MAX_VALUE;
        int rightMin = node.right != null ? getMin(node.right, minMap) : Integer.MAX_VALUE;

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

        minMap.put(node, min);
        return min;
    }
}
//leetcode submit region end(Prohibit modification and deletion)