遞歸
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode node, long lower, long upper) {
if (node == null) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}
}
一:
二:
中序周遊
中序周遊,看是否是升序
一開始定義一個最小數,然後讓中序周遊的一次從前開始和他比,并把讓他依次等于中序中的數與後一個數比較,提高效率
class Solution {
long pre = Long.MIN_VALUE;//A constant holding the minimum value a long can have, -263. 保持 long 類型的最小值的常量,該值為 -263。
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 通路左子樹
if (!isValidBST(root.left)) {
return false;
}
// 通路目前節點:如果目前節點小于等于中序周遊的前一個節點,說明不滿足BST,傳回 false;否則繼續周遊。
if (root.val <= pre) {
return false;
}
pre = root.val;
// 通路右子樹
return isValidBST(root.right);
}
}