Leetcode 98
    https://leetcode-cn.com/problems/validate-binary-search-tree/

    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 node’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

    1. class Solution {
    2.     // 递归
    3.     TreeNode max;
    4.     public boolean isValidBST(TreeNode root) {
    5.         if (root == null) {
    6.             return true;
    7.         }
    8.         // 左
    9.         boolean left = isValidBST(root.left);
    10.         if (!left) {
    11.             return false;
    12.         }
    13.         // 中
    14.         if (max != null && root.val <= max.val) {
    15.             return false;
    16.         }
    17.         max = root;
    18.         // 右
    19.         boolean right = isValidBST(root.right);
    20.         return right;
    21.     }
    22. }
    1. class Solution {
    2.     // 迭代
    3.     public boolean isValidBST(TreeNode root) {
    4.         if (root == null) {
    5.             return true;
    6.         }
    7.         Stack<TreeNode> stack = new Stack<>();
    8.         TreeNode pre = null;
    9.         while (root != null || !stack.isEmpty()) {
    10.             while (root != null) {
    11.                 stack.push(root);
    12.                 root = root.left;// 左
    13.             }
    14.             // 中，处理
    15.             TreeNode pop = stack.pop();
    16.             if (pre != null && pop.val <= pre.val) {
    17.                 return false;
    18.             }
    19.             pre = pop;
    21.             root = pop.right;// 右
    22.         }
    23.         return true;
    24.     }
    25. }