Java Solution beats 80%


  • 0
    L
     public class Solution {
     private int max;
     public int largestBSTSubtree(TreeNode root) {
         largestStartAt(root);
         return max;
     }    
    
     public int largestStartAt(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = largestStartAt(root.left);
        int right = largestStartAt(root.right);
        if (left == -1 || right == -1) {
            return -1;
        }
        TreeNode cur = root.left;
        while (cur != null && cur.right != null) {
            cur = cur.right;
        }
        int lo = cur == null ? Integer.MIN_VALUE : cur.val;
        
        cur = root.right;
        while (cur != null && cur.left != null) {
            cur = cur.left;
        }
        int hi = cur == null ? Integer.MAX_VALUE : cur.val;
        if (root.val > lo && root.val < hi) {
            max = Math.max(max, left + right + 1);
            return left + right + 1;
        }
        return -1;
    }
    

    }


Log in to reply
 

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