Java O(n) clear solution with comments


  • 2
    public class Solution {
        public int largestBSTSubtree(TreeNode root) {
            return largestBSTSubtreeHelper(root).size;
        }
        
        private Node largestBSTSubtreeHelper(TreeNode root) {
            if (root == null) {
                return new Node(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);//fake node for null
            }
            Node nodeL = largestBSTSubtreeHelper(root.left);
            Node nodeR = largestBSTSubtreeHelper(root.right);
            if (nodeL.isValid && nodeR.isValid && nodeL.max < root.val && nodeR.min > root.val) {
                return new Node(true, nodeL.size + nodeR.size + 1, Math.min(nodeL.min, root.val), Math.max(nodeR.max, root.val));
            }
            // above we use Math.min(nodeL.min, root.val) instead of just nodeL.min is because we use Integer.MAX_VALUE 
            //for the fake null node and we need to find the true min which is root.val.
            return new Node(false, Math.max(nodeL.size, nodeR.size), root.val, root.val);
        }
    }
    
    class Node {
        boolean isValid;
        int size;
        int min;
        int max;
        Node(boolean v, int s, int min, int max) {
            isValid = v;
            size = s;
            this.min = min;
            this.max = max;
        }
    }

Log in to reply
 

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