# LeetCode 98. Validate Binary Search Tree

### 解法一

##### 代码
``````class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
TreeNode prev = null;

// Do an inorder traversal
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}

curr = stack.pop();
if (prev != null && prev.val >= curr.val) {
return false;
}
prev = curr;
curr = curr.right;
}
return true;
}
}``````
##### 复杂度分析
• 时间复杂度
• 遍历一遍二叉树，花费 O(n) 时间
• 空间复杂度
• O(N) – Stack

### 解法二

##### 代码
``````class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}

private boolean helper(TreeNode node, Integer lower, Integer upper) {
if (node == null) return true;
int val = node.val;
if (lower != null && val <= lower) return false;
if (upper != null && val >= upper) return false;

// recursively check left and right subtree
if (!helper(node.left, lower, val)) return false;
if (!helper(node.right, val, upper)) return false;

return true;
}
}``````
• 时间复杂度
• O(n)
• 空间复杂度
• O(n)

(=￣ω￣=)··· 暂无内容！

52

4

10

16