LeetCode 98. Validate Binary Search Tree
解法一
思路
中序遍历BST可以得到有序数组,所以如果遍历时前一个数比后一个数大的话,就不是 valid 了。
代码
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
TreeNode prev = null;
// Do an inorder traversal
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
if (prev != null && prev.val >= curr.val) {
return false;
}
prev = curr;
curr = curr.right;
}
return true;
}
}
复杂度分析
- 时间复杂度
- 遍历一遍二叉树,花费 O(n) 时间
- 空间复杂度
- O(N) – Stack
解法二
思路
写一个 helper function, 先检查该结点是否比 upper bound 小,以及比 lower bound 大;然后递归调用检查其左子树和右子树。
代码
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}
private boolean helper(TreeNode node, Integer lower, Integer upper) {
if (node == null) return true;
int val = node.val;
if (lower != null && val <= lower) return false;
if (upper != null && val >= upper) return false;
// recursively check left and right subtree
if (!helper(node.left, lower, val)) return false;
if (!helper(node.right, val, upper)) return false;
return true;
}
}
复杂度分析
- 时间复杂度
- O(n)
- 空间复杂度
- O(n)
Takeaway
由于是 BST,必须保证每一个节点的所有左孩子比它小,右孩子比它大。
本作品采用《CC 协议》,转载必须注明作者和本文链接