验证二叉搜索树

[chaojun-zhang]

递归遍历

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root==null) return true;
        return helper(root.left,Long.MIN_VALUE,root.val) && helper(root.right,root.val,Long.MAX_VALUE);
    }

    private boolean helper(TreeNode node ,long low,long high){
        if (node ==null) return true;
        if (node.val<=low || node.val>= high) return false;
        return helper(node.left,low,node.val) && helper(node.right,node.val,high);

    }
}

中序遍历法 当前遍历的元素必须大于上一个元素

class Solution {
  public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    double inorder = - Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // If next element in inorder traversal
      // is smaller than the previous one
      // that's not BST.
      if (root.val <= inorder) return false;
      inorder = root.val;
      root = root.right;
    }
    return true;
  }
}