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:
這道題目還是比較簡(jiǎn)單的杖狼，但是還是過(guò)了好幾次才pass披蕉。這是不好的
同時(shí)，一個(gè)細(xì)節(jié)就是伞访，測(cè)試案例中出現(xiàn)了掂骏，一個(gè)結(jié)點(diǎn)，Integer.MIN_VALUE 的情況厚掷。所以過(guò)不了弟灼。所以级解， pre 一定得是比int最小值還小的值，即田绑， Long.MIN_VALUE
**
總結(jié)： 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;
}
}
就是設(shè)定一個(gè)范圍民逼。
沒(méi)什么意思。
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;
}
}
不知道為什么焚辅，同等時(shí)間復(fù)雜度的算法映屋，iteration 總是要比 recursion慢一些。
Anyway, Good luck, Richardo! -- 09/06/2016
