Largest BST Subtree

Leave a comment

December 1, 2016 by oneOokay

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.
The return value is the subtree’s size, which is 3.


相关:Validate Binary Search Tree

找到一棵树中最大的BST(包含最多node数目的)

两种方法:

  1. 自身迭代切用判断是否是valid BST的方法来做
    • 一个isValid() 来判断以当前node为root的树时候是一个validBST
      • 如果是的话,返回 countNodes()
      • 如果不是:返回largestBSTSubtree(node.left)和largestBSTSubtree(node.right)中的较大值
  2. DFS:从底向上时间为O(n),我觉得这个从底向上的方法以及validate的方法很好。
    • 用一个Result class:
      • 一个int 来存以当前node为root的一个subtree它的largestBST的count
      • 一个boolean 来标示以当前node为root的一个subtree是否是一个valid BST
      • 另两个TreeNode代表如果以前欠node为root的一个subtree是一个valid的BST的话那么它的最小的Min TreeNode和Max TreeNode.
        • 用TreeNode是不想用Integer.MAX_VALUE和Integer.MIN_VALUE
方法一:
public int largestBSTSubtree(TreeNode root) {
 if (root == null) return 0;
 if (root.left == null && root.right == null) return 1;
 if (isValid(root, null, null)) return countNode(root);
 return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
}

public boolean isValid(TreeNode root, Integer min, Integer max) {
 if (root == null) return true;
 if (min != null && min >= root.val) return false;
 if (max != null && max <= root.val) return false;
 return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
}

public int countNode(TreeNode root) {
 if (root == null) return 0;
 if (root.left == null && root.right == null) return 1;
 return 1 + countNode(root.left) + countNode(root.right);
}

方法二:
public int largestBSTSubtree(TreeNode root) {
 Result res = helper(root);
 return res.count;
 }
 
 private Result helper(TreeNode node){
//如果一个node是叶子节点的话,它的left和right就会是这个node == null的返回结果 
if (node == null) return new Result(0, true, null, null);
 
 Result left = helper(node.left);
 Result right = helper(node.right);
 if (!left.isValid || !right.isValid || left.max != null && left.max.val >= node.val || right.min != null && right.min.val <= node.val){
//如果当前的树不是一个valid的BST,返回左右结果中最大的count作为result的count值 
return new Result(Math.max(left.count, right.count), false, null, null);
 }
//是一个validBST:注意如果left.min==null的话
(这个时候left.right也会是null),说明node是没有左儿子的,所以此时的min应该为node本身
同样的对于right.max == null的判断
 return new Result(left.count + right.count + 1, true, left.min == null?node:left.min, right.max == null?node:right.max);
 }
 
 private class Result{
 int count;
 boolean isValid;
 TreeNode max;
 TreeNode min;
 Result(int count, boolean isValid, TreeNode n1, TreeNode n2){
 this.count = count;
 this.isValid = isValid;
 min = n1;
 max = n2;
 }
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: