# 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a 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:
2
/ \
1   3
Output: true
``````

Example 2:

``````    5
/ \
1   4
/ \
3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
``````

C++ 解法一：

``````// Recursion without inorder traversal
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
bool isValidBST(TreeNode* root, long mn, long mx) {
if (!root) return true;
if (root->val <= mn || root->val >= mx) return false;
return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
}
};
``````

Java 解法一：

``````public class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean valid(TreeNode root, long low, long high) {
if (root == null) return true;
if (root.val <= low || root.val >= high) return false;
return valid(root.left, low, root.val) && valid(root.right, root.val, high);
}
}
``````

20       20
/           \
20           20

C++ 解法二：

``````// Recursion
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
vector<int> vals;
inorder(root, vals);
for (int i = 0; i < vals.size() - 1; ++i) {
if (vals[i] >= vals[i + 1]) return false;
}
return true;
}
void inorder(TreeNode* root, vector<int>& vals) {
if (!root) return;
inorder(root->left, vals);
vals.push_back(root->val);
inorder(root->right, vals);
}
};
``````

Java 解法二：

``````public class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
inorder(root, list);
for (int i = 0; i < list.size() - 1; ++i) {
if (list.get(i) >= list.get(i + 1)) return false;
}
return true;
}
public void inorder(TreeNode node, List<Integer> list) {
if (node == null) return;
inorder(node.left, list);
inorder(node.right, list);
}
}
``````

C++ 解法三：

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode *pre = NULL;
return inorder(root, pre);
}
bool inorder(TreeNode* node, TreeNode*& pre) {
if (!node) return true;
bool res = inorder(node->left, pre);
if (!res) return false;
if (pre) {
if (node->val <= pre->val) return false;
}
pre = node;
return inorder(node->right, pre);
}
};
``````

C++ 解法四：

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> s;
TreeNode *p = root, *pre = NULL;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
if (pre && p->val <= pre->val) return false;
pre = p;
p = p->right;
}
return true;
}
};
``````

Java 解法四：

``````public class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode p = root, pre = null;
while (p != null || !s.empty()) {
while (p != null) {
s.push(p);
p = p.left;
}
p = s.pop();
if (pre != null && p.val <= pre.val) return false;
pre = p;
p = p.right;
}
return true;
}
}
``````

C++ 解法五:

``````class Solution {
public:
bool isValidBST(TreeNode *root) {
if (!root) return true;
TreeNode *cur = root, *pre, *parent = NULL;
bool res = true;
while (cur) {
if (!cur->left) {
if (parent && parent->val >= cur->val) res = false;
parent = cur;
cur = cur->right;
} else {
pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
if (parent->val >= cur->val) res = false;
parent = cur;
cur = cur->right;
}
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/98

Binary Tree Inorder Traversal

Find Mode in Binary Search Tree

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

https://leetcode.com/problems/validate-binary-search-tree/discuss/32101/My-java-inorder-iteration-solution

https://leetcode.com/problems/validate-binary-search-tree/discuss/32109/My-simple-Java-solution-in-3-lines

https://leetcode.com/problems/validate-binary-search-tree/discuss/32112/Learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-(Java-Solution)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation