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.
一开始是这样做的：
class Solution {
public:
bool isValidBST(TreeNode* root) {
return checkValid(root, INT_MIN, INT_MAX);
}
bool checkValid(TreeNode * root, int left, int right)
{
if(root == NULL)
return true;
return(root->val > left && root->val < right && checkValid(root->left, left, root->val) ]
&& checkValid(root->right, root->val, right));
}
};
然而并不能通过，因为leetCode增加了两个新的测试用例，把INT_MAX以及INT_MIN也囊括进去了。
那么就只好用中序遍历的方法来了(一开始想的是先中序遍历一遍，然后根据遍历的到的值是不是升序排列的来判断这个二叉树是不是BST，但是后来发现传入一个引用的参数可以实现一边递归一边比较)，代码如下：
class Solution{
public:
bool isValidBST(TreeNode* root) {
TreeNode * helper = NULL;
return inOrder(root, helper);
}
bool inOrder(TreeNode * root, TreeNode * & prev){//注意这里的是引用
if(root == NULL)
return true;
bool left = inOrder(root->left, prev);
if(prev != NULL && prev->val >= root->val)
return false;
prev = root;
bool right = inOrder(root->right, prev);
return left && right;
}
};
当然上面的也可以采用迭代的方式来做:
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode *> s;
TreeNode * pre = NULL;
if(root == NULL)
return true;
while(root || !s.empty()){
while(root != NULL){
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if(pre != NULL && root->val <= pre->val) return false;
pre = root;
root = root->right;
}
return true;
}
};
下面是java版本的代码，首先还是不可行的Integer.MAX_VALUE方法，但是还是贴下吧：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
return checkValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
} boolean checkValid(TreeNode root, int left, int right){
if(root == null)
return true;
if(root.val <= left || root.val >= right){
return false;
}
return checkValid(root.left, left, root.val)
&& checkValid(root.right, root.val, right);
}
}
那么只有遍历树了，然后来判断, 这里使用非递归的方法来写:
public class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
List<Integer> list = new ArrayList<Integer>();
if(root == null)
return true;
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.peek();
while(node.left != null && !map.containsKey(node.left)){
stack.push(node.left);
map.put(node.left, 1);
node = node.left;
}
stack.pop();
list.add(node.val);
if(node.right != null && !map.containsKey(node.right)){
stack.push(node.right);
map.put(node.right, 1);
}
}
for(int i = 0; i < list.size() - 1; ++i){
if(list.get(i) >= list.get(i+1))
return false;
}
return true;
}
}