Tuesday, June 7, 2016

Leetcode: 333. Largest BST Subtree

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.
Hint:
  1. You can recursively use algorithm similar to 98. 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?
Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = 0;
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        largestBSTHelper(root);
        
        return max;
    }
    
    private Data largestBSTHelper(TreeNode root) {
        Data curr = new Data();
        if (root == null) {
            curr.isBST = true;
            return curr;
        }
        
        Data left = largestBSTHelper(root.left);
        Data right = largestBSTHelper(root.right);
        
        curr.lower = Math.min(root.val, Math.min(left.lower, right.lower));
        curr.upper = Math.max(root.val, Math.max(left.upper, right.upper));
        
        if (left.isBST && root.val > left.upper && right.isBST && root.val < right.lower) {
            curr.size = left.size + right.size + 1;
            curr.isBST = true;
            max = Math.max(max, curr.size);
        } else {
            curr.size = 0;
        }
        
        return curr;
    }
}

class Data {
    int size = 0;
    int lower = Integer.MAX_VALUE;
    int upper = Integer.MIN_VALUE;
    boolean isBST = false;
}

No comments:

Post a Comment