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.
解題思路
一開始想當然用遞歸的思想罩句，如果左子樹的值小于根節(jié)點且同時又滿足右子樹的值大于根節(jié)點久脯，就繼續(xù)遞歸，否則返回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;
}
}```
但是運行后發(fā)現(xiàn)了問題。這段代碼中我只關心了某一個節(jié)點是否符合要求排吴。而縱觀全局众眨，所有的根節(jié)點右邊的數(shù)字都應該大于根節(jié)點。思考之后阻逮，我設立一個取值范圍粱快，用于遞歸中。
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;
}
第三種方法寫起來更簡單，但是如果錯誤就發(fā)生在根節(jié)點附近事哭，那它要慢于第二種的速度漫雷。
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);
}
以上都是用的遞歸的思想來解決問題，現(xiàn)在利用廣度優(yōu)先遍歷的思想來解決鳍咱。
廣度優(yōu)先搜索算法需要用到隊列降盹。具體請參考以下鏈接：
public class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
//利用一個隊列來存儲節(jié)點。
LinkedList<BNode> queue = new LinkedList<BNode>();
//初始化調(diào)用谤辜，根節(jié)點的取值范圍是負無窮到正無窮
queue.add(new BNode(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
while(!queue.isEmpty()){
//從隊列里彈出一個節(jié)點
BNode b = queue.poll();
if(b.n.val <= b.left || b.n.val >=b.right){
return false;
}
if(b.n.left!=null){
//添加一個新的節(jié)點蓄坏。
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;
}
}
