思路

递归

上述思路可以用递归法实现。首先将结点的值与上界和下界（如果有）比较。然后，对左子树和右子树递归进行该过程。

class Solution {
    //递归辅助函数 需要判断的是上下界的关系
     public boolean helper(TreeNode root,Integer lower,Integer upper){
        if(root==null)   //如果根为空 返回true
            return true;
        int val = root.val;
        //判断上界和值的关系 不满足返回false
        if(lower!=null&&val<=lower) return false;
        if(upper!=null&&val>=upper) return false;
        //递归判断左右子树，对右子树设置其下界 对左子树设置其上界
        if(!helper(root.right,val,upper)) return false;
        if(!helper(root.left,lower,val)) return false;
        //如果左右子树都满足的话 则返回true
        return true;
    }
    public boolean isValidBST(TreeNode root) {
        //设置一个辅助函数 上界和下界初始化为null
        return helper(root,null,null);
    }
}

迭代

使用栈的辅助来替代上面的迭代过程

class Solution {
  LinkedList<TreeNode> stack = new LinkedList();
  LinkedList<Integer> uppers = new LinkedList(),
          lowers = new LinkedList();

  public void update(TreeNode root, Integer lower, Integer upper) {
    stack.add(root);
    lowers.add(lower);
    uppers.add(upper);
  }

  public boolean isValidBST(TreeNode root) {
    Integer lower = null, upper = null, val;
    update(root, lower, upper);

    while (!stack.isEmpty()) {
      root = stack.poll();
      lower = lowers.poll();
      upper = uppers.poll();

      if (root == null) continue;
      val = root.val;
      if (lower != null && val <= lower) return false;
      if (upper != null && val >= upper) return false;
      update(root.right, val, upper);
      update(root.left, lower, val);
    }
    return true;
  }
}