Sharing Simplest Java Solution. Very Simple and Easy to Understand!


  • -1
    L

    Breaking down the problem into 3 subproblems: Checking if a subtree is valid, Finding the size of a tree, and Finding the Largest BST Subtree.

    Idea: Check if each subtree is valid, if so, return count. Otherwise, recursively call on the left and right subtrees. This is O(n^2).

    /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
     */
    public class Solution {
       
       public int largestBSTSubtree(TreeNode root) {
           if(root == null) return 0;
           if(isValid(root, Integer.MAX_VALUE, Integer.MIN_VALUE)) return count(root);
           else return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
       }
        
       public int count (TreeNode n){
           if(n == null)
               return 0;
           return 1 + count(n.left) + count(n.right);
       }
       
       public boolean isValid(TreeNode n, int max, int min){
           if(n == null) return true;
           if(n.val < max && n.val > min) return isValid(n.left, n.val, min) && isValid(n.right, max, n.val);
           else return false;
       }
       
    }

  • -1
    Q

    Are you sure its time complexity is N^2? In worst case, the leaf nodes will be scanned logN times. Actually, your root(first level) is scanned once and the children(second level) of root is scanned twice. The third level will be scanned three times. The leaf nodes will be scanned logN times. So why it is N^2 time complexity


  • 0
    W

    What if the tree is degenerative (i.e. like a linked list branching left)? Worst case would converge to n^2 no? .

    Improvement to this solution would be to pass down Integer objects rather than int into validate. Max/Min Int could be an actual value in the tree. But this was more or less the default solution I was thinking of.

    Curious though if it can be improved by running an inorder traversal and checking for the longest running monotonically increasing sequence? That's the only way I could think of getting O(n) off hand. Although it might not be the correct solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.