My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private boolean isValid = true;
private long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
inorder(root);
return isValid;
}
private void inorder(TreeNode root) {
if (root.left != null) {
inorder(root.left);
}
if (pre < root.val)
pre = root.val;
else
isValid = false;
if (root.right != null) {
inorder(root.right);
}
}
}
My test result:
这道题目还是比较简单的，但是还是过了好几次才pass。这是不好的
同时，一个细节就是，测试案例中出现了，一个结点，Integer.MIN_VALUE 的情况。所以过不了。所以， pre 一定得是比int最小值还小的值，即， Long.MIN_VALUE
**
总结： BST 的inorder 遍历。
**
Anyway, Good luck, Richardo!
My code:
/**
* 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) {
if (root == null)
return true;
long min = (long) Integer.MIN_VALUE - 1;
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode node = root;
while (node != null) {
s.push(node);
node = node.left;
}
while (!s.isEmpty()) {
node = s.pop();
if (node.val <= min)
return false;
min = node.val;
node = node.right;
while (node != null) {
s.push(node);
node = node.left;
}
}
return true;
}
}
这里使用了 非递归，外加min。解决。
也可以递归加min。
下面再展示一种做法。
My code:
/**
* 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) {
if (root == null)
return true;
long min = ((long) Integer.MIN_VALUE) - 1;
long max = ((long) Integer.MAX_VALUE) + 1;
return isValidBST(root, min, max);
}
private boolean isValidBST(TreeNode root, long min, long max) {
if (root == null)
return true;
if (root.val > min && root.val < max) {
return isValidBST(root.left, min, (long) root.val) && isValidBST(root.right, (long) root.val, max);
}
return false;
}
}
就是设定一个范围。
没什么意思。
Anyway, Good luck, Richardo!
My code:
/**
* 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 check(root, (long) Integer.MIN_VALUE - 1, (long) Integer.MAX_VALUE + 1);
}
private boolean check(TreeNode root, long min, long max) {
if (root == null) {
return true;
}
else if (root.val > min && root.val < max) {
return check(root.left, min, root.val) && check(root.right, root.val, max);
}
else {
return false;
}
}
}
这是 dfs 的做法。更像是一种层序遍历。
父亲必须加在左右孩子之间，一层层往下检查
下面是 中序遍历 recursion检查：
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
long pre = (long) Integer.MIN_VALUE - 1;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (isValidBST(root.left)) {
if (root.val > pre) {
pre = root.val;
return isValidBST(root.right);
}
}
return false;
}
}
pre-order iteration
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
long pre = (long) Integer.MIN_VALUE - 1;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> st = new Stack<TreeNode>();
TreeNode p = root;
while (p != null) {
st.push(p);
p = p.left;
}
while (!st.isEmpty()) {
TreeNode curr = st.pop();
if (curr.val <= pre) {
return false;
}
pre = curr.val;
if (curr.right != null) {
curr = curr.right;
while (curr != null) {
st.push(curr);
curr = curr.left;
}
}
}
return true;
}
}
不知道为什么，同等时间复杂度的算法，iteration 总是要比 recursion慢一些。
Anyway, Good luck, Richardo! -- 09/06/2016
