version1

思路：验证二叉搜索树等价于中序遍历有序，可以用递归中序遍历（代码简洁），也可以用迭代中序遍历（效率高）。

version2

思路：递归中序遍历，自顶向下设计，每一颗树均不超过指定的范围：[min, max]

  1. public class Solution98 {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
  4.     }
  6.     public boolean validate(TreeNode root, long min, long max){
  7.         if (root == null) {
  8.             return true;
  9.         }
  10.         if(root.val <= min || root.val >= max){
  11.             return false;
  12.         }
  13.         return validate(root.left, min, root.val) && validate(root.right, root.val, max);
  14.     }
  15. }

version3（不推荐）

思路：递归中序遍历，自底向上设计，每次访问子树均返回这棵子树上的最大值、最小值以及子树是否是合法的结果。

  1. public class Solution98 {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return findMaxAndMin(root).get("isValid") == 1;
  4.     }
  6.     public Map<String, Integer> findMaxAndMin(TreeNode root){
  7.         Map<String, Integer> ret = new HashMap<>();
  8.         Map<String, Integer> leftRet;
  9.         Map<String, Integer> rightRet;
  10.         if (root.left == null) {
  11.             leftRet = new HashMap<>();
  12.             leftRet.put("max", Integer.MIN_VALUE);
  13.             leftRet.put("min", root.val);
  14.             leftRet.put("isValid", 1);
  15.         }else{
  16.             leftRet = findMaxAndMin(root.left);
  17.         }
  18.         if(root.right == null){
  19.             rightRet = new HashMap<>();
  20.             rightRet.put("max", root.val);
  21.             rightRet.put("min", Integer.MAX_VALUE);
  22.             rightRet.put("isValid", 1);
  23.         }else {
  24.             rightRet = findMaxAndMin(root.right);
  25.         }
  26.         boolean isValid = true;
  27.         if(root.left == null && root.val == Integer.MIN_VALUE){
  28.         }else {
  29.             isValid = leftRet.get("isValid") ==1 && leftRet.get("max") < root.val;
  30.         }
  31.         if(root.right == null && root.val == Integer.MAX_VALUE){
  32.         }else {
  33.             isValid = isValid && rightRet.get("isValid") == 1 && rightRet.get("min") > root.val;
  34.         }
  35.         if(isValid){
  36.             ret.put("max", rightRet.get("max"));
  37.             ret.put("min", leftRet.get("min"));
  38.             ret.put("isValid", 1);
  39.         }else{
  40.             ret.put("isValid", 0);
  41.         }
  42.         return ret;
  43.     }
  44. }