leetcode 98 Validate Binary Search Tree
Problem:
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.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.
解题思路
一开始想当然用递归的思想，如果左子树的值小于根节点且同时又满足右子树的值大于根节点，就继续递归，否则返回false。代码如下。
public class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null){
return true;
}
if(root.left!=null && (root.left.val>root.val || !isValidBST(root.left))){
return false;
}
if(root.right!=null && (root.right.val<root.val || !isValidBST(root.right))){
return false;
}
return true;
}
}```
但是运行后发现了问题。这段代码中我只关心了某一个节点是否符合要求。而纵观全局，所有的根节点右边的数字都应该大于根节点。思考之后，我设立一个取值范围，用于递归中。
public boolean isValidBST(TreeNode root) {
if(root==null)
return true;
return helper(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
}
public boolean helper(TreeNode root, double low, double high){
if(root.val<=low || root.val>=high)
return false;
if(root.left!=null && !helper(root.left, low, root.val)){
return false;
}
if(root.right!=null && !helper(root.right, root.val, high)){
return false;
}
return true;
}
第三种方法写起来更简单，但是如果错误就发生在根节点附近，那它要慢于第二种的速度。
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
}
public boolean isValidBST(TreeNode p, double min, double max){
if(p==null)
return true;
if(p.val <= min || p.val >= max)
return false;
return isValidBST(p.left, min, p.val) && isValidBST(p.right, p.val, max);
}
以上都是用的递归的思想来解决问题，现在利用广度优先遍历的思想来解决。
广度优先搜索算法需要用到队列。具体请参考以下链接：
public class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
//利用一个队列来存储节点。
LinkedList<BNode> queue = new LinkedList<BNode>();
//初始化调用，根节点的取值范围是负无穷到正无穷
queue.add(new BNode(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
while(!queue.isEmpty()){
//从队列里弹出一个节点
BNode b = queue.poll();
if(b.n.val <= b.left || b.n.val >=b.right){
return false;
}
if(b.n.left!=null){
//添加一个新的节点。
queue.offer(new BNode(b.n.left, b.left, b.n.val));
}
if(b.n.right!=null){
queue.offer(new BNode(b.n.right, b.n.val, b.right));
}
}
return true;
}
}
//define a BNode class with TreeNode and it's boundaries
class BNode{
TreeNode n;
double left;
double right;
public BNode(TreeNode n, double left, double right){
this.n = n;
this.left = left;
this.right = right;
}
}
#leetcode 333 [Largest BST Subtree](https://leetcode.com/problems/largest-bst-subtree/)
#####Problem:
Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Note:A subtree must include all of its descendants.Here's an example:
10
/ \
5 15
/ \ \
1 8 7
The Largest BST Subtree in this case is the highlighted one(5,1,8. The return value is the subtree's size, which is 3.
Hint:
You can recursively use algorithm similar to [98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) at each node of the tree, which will result in O(nlogn) time complexity.
Follow up:Can you figure out ways to solve it with O(n) time complexity?
class Wrapper{
int size;
int lower, upper;
boolean isBST;
public Wrapper(){
lower = Integer.MAX_VALUE;
upper = Integer.MIN_VALUE;
isBST = false;
size = 0;
}
}
public class Solution {
public int largestBSTSubtree(TreeNode root) {
return helper(root).size;
}
public Wrapper helper(TreeNode node){
Wrapper curr = new Wrapper();
if(node == null){
curr.isBST= true;
return curr;
}
Wrapper l = helper(node.left);
Wrapper r = helper(node.right);
//current subtree's boundaries
curr.lower = Math.min(node.val, l.lower);
curr.upper = Math.max(node.val, r.upper);
//check left and right subtrees are BST or not
//check left's upper again current's value and right's lower against current's value
if(l.isBST && r.isBST && l.upper<=node.val && r.lower>=node.val){
curr.size = l.size+r.size+1;
curr.isBST = true;
}else{
curr.size = Math.max(l.size, r.size);
curr.isBST = false;
}
return curr;
}
}
