Given a binary tree, determine if it is a valid binary search tree (BST).
对于每一个子树，限制它的最大，最小值，如果超过则返回false。对于根节点，最大最小都不限制；
每一层节点，左子树限制最大值小于根，右子树最小值大于根；
但是比较有趣的是，在递归的过程中还得不断带入祖父节点的值。
或者，中序遍历该树，然后扫描一遍看是否递增。
bool isValidBST(TreeNode *root) {
return IsValidBST(root, INT_MIN, INT_MAX);
}
bool IsValidBST(TreeNode* node, int MIN, int MAX)
{
if(node == NULL)
return true;
if(node->val > MIN
&& node->val < MAX
&& IsValidBST(node->left,MIN,node->val)
&& IsValidBST(node->right,node->val,MAX))
return true;
else
return false;
}
From: http://yucoding.blogspot.com/2013/02/leetcode-question-122-validate-binary.html
void inOrder(TreeNode* root, int &pre, bool &res){ if (!root || !res ){return;} inOrder(root->left,pre,res); if (pre>=root->val){ res = false; return; }else{ pre = root->val; } inOrder(root->right,pre,res); } bool isValidBST(TreeNode *root) { if (!root){return true;} int pre = INT_MIN; bool res=true; inOrder(root,pre,res); return res; }EPI Solution: Test if a binary tree satisfies the BST property
IsBinaryTreeABST.javapublic static boolean isBST(BinaryTree<Integer> root) {
return isBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private static boolean isBSTHelper(BinaryTree<Integer> root,
Integer lower, Integer upper) {
if (root == null) {
return true;
} else if (root.getData().compareTo(lower) < 0
|| root.getData().compareTo(upper) > 0) {
return false;
}
return isBSTHelper(root.getLeft(), lower, root.getData())
&& isBSTHelper(root.getRight(), root.getData(), upper);
}
IsBinaryTreeABSTConstSpace.java
public static boolean isBST(BinaryTree<Integer> root) {
BinaryTree<Integer> n = root;
// Stores the value of previous visited node.
Integer last = Integer.MIN_VALUE;
boolean result = true;
while (n != null) {
if (n.getLeft() != null) {
// Finds the predecessor of n.
BinaryTree<Integer> pre = n.getLeft();
while (pre.getRight() != null && pre.getRight() != n) {
pre = pre.getRight();
}
// Processes the successor link.
if (pre.getRight() != null) { // pre.getRight() == n.
// Reverts the successor link if predecessor's successor is n.
pre.setRight(null);
if (last.compareTo(n.getData()) > 0) {
result = false;
}
last = n.getData();
n = n.getRight();
} else { // If predecessor's successor is not n.
pre.setRight(n);
n = n.getLeft();
}
} else {
if (last.compareTo(n.getData()) > 0) {
result = false;
}
last = n.getData();
n = n.getRight();
}
}
return result;
}
isBinaryTreeABST_BFS.java
public static class QNode {
public BinaryTree<Integer> node;
public Integer lower, upper;
public QNode(BinaryTree<Integer> node, Integer lower, Integer upper) {
this.node = node;
this.lower = lower;
this.upper = upper;
}
}
public static boolean isBST(BinaryTree<Integer> r) {
LinkedList<QNode> q = new LinkedList<>();
q.addLast(new QNode(r, Integer.MIN_VALUE, Integer.MAX_VALUE));
while (!q.isEmpty()) {
if (q.getFirst().node != null) {
if (q.getFirst().node.getData().compareTo(q.getFirst().lower) < 0
|| q.getFirst().node.getData().compareTo(q.getFirst().upper) > 0) {
return false;
}
q.addLast(new QNode(q.getFirst().node.getLeft(), q.getFirst().lower,
q.getFirst().node.getData()));
q.addLast(new QNode(q.getFirst().node.getRight(),
q.getFirst().node .getData(), q.getFirst().upper));
}
q.removeFirst();
}
return true;
}
Read full article from 水中的鱼: [LeetCode] Validate Binary Search Tree 解题报告
