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.

Similar to Leetcode.98

Test Case 

1
2
3
4
5
6
7
8
9
10
11
Input: [10,5,15,1,8,null,7]

   10 
   / \ 
  5  15 
 / \   \ 
1   8   7

Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
             The return value is the subtree's size, which is 3.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

logic

    1. dfs, get the information from bottom(top down), should return the max value in the left node and the min value in the right node.
    1. a inner class is useful for the data

  • inner class:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Res{
            int size;
            int lower;
            int upper;
            Res(int size, int lower, int upper){
                this.size = size;
                this.lower = lower;
                this.upper = upper;
            }
        }

  • main method:

    1
    2
    3
    4
    5
    public int largestBSTSubtree(TreeNode root) {
            if(root==null) return 0;
            dfs(root);
            return max;
        }

  • dfs treversal

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    private Res dfs(TreeNode root){
        //fullfill the tree rule but the size = 0
        if(root==null) {return new Res(0, Integer.MAX_VALUE, Integer.MIN_VALUE);}
        Res left = dfs(root.left);
        Res right = dfs(root.right);
        //not fullfill the tree rule and size = -1 and the lower and upper is 0;
        if(left.size==-1 || right.size == -1 || root.val <= left.upper || root.val >= right.lower)
            return new Res(-1, 0, 0);
        int size = left.size + 1 + right.size;
        max = Math.max(size, max);
        return new Res(size, Math.min(left.lower, root.val), Math.max(right.upper, root.val));
    }

the other way is to use parent as para in the dfs instead of use max and min value.

Leetcode.98 Validate the BST tree

DFS search

1
2
3
4
5
6
7
8
9
10
public class Solution{
    public boolean isValidBST(root, long minVal, long maxVal){
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode root, long minVal, long maxVal){
        if(root==null) return true;
        if(root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}