Java bottom up solution, relatively clear but with some copy-paste


  • 0
    A

    I'm a bit lazy and dont' want to spend time to remove copy paste from conditions, but, actually, I think that it makes code a bit clearer

    public class Solution {
        int maxValue = 0;
        
        public int largestBSTSubtree(TreeNode root) {
            if (root == null)
                return 0;
            
            largeBST(root);
            return maxValue;
        }
    
        private int[] largeBST(TreeNode n) {
            int[] res = new int[]{n.val, n.val, 1};
    
            if (n.left == null && n.right == null) {
                maxValue = Math.max(maxValue, res[2]);
                return res;
            }
    
            int[] left, right;
            if (n.left == null) {
                right = largeBST(n.right);
    
                if (right == null || right[0] < n.val) {
                    return null;
                }
    
                res[1] = right[1];
                res[2]+= right[2];
                maxValue = Math.max(maxValue, res[2]);
                return res;
            }
    
            if (n.right == null) {
                left = largeBST(n.left);
                if (left == null || left[1] > n.val) {
                    return null;
                }
                res[0] = left[0];
                res[2] += left[2];
                maxValue = Math.max(maxValue, res[2]);
                return res;
            }
    
    
            left = largeBST(n.left);
            right = largeBST(n.right);
    
            if (right == null || right[0] < n.val) {
                return null;
            }
            if (left == null || left[1] > n.val) {
                return null;
            }
    
            res[0] = left[0];
            res[1] = right[1];
            res[2] = res[2] + left[2] + right[2];
            maxValue = Math.max(maxValue, res[2]);
            return res;
        }
    }

  • 0
    V
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    int myMax(int a, int b) {
        int c;
        c = (a > b) ? a : b;
        return(c);
    }
     
     int largestBSTHelper(struct TreeNode *root, int *min, int *max, int *largest) {
        int lMin, lMax, rMin, rMax;
        int count, lCount, rCount;
        
        lMin = lMax = rMin= rMax = root->val;
        
        if (NULL == root->left && NULL == root->right) {
            *min = root->val;
            *max = root->val;
            count = 1;
            *largest = myMax(*largest, count);
            return(count);
        }
        
        lCount = (root->left == NULL) ? 0 : largestBSTHelper(root->left, &lMin, &lMax, largest);
        rCount = (root->right == NULL) ? 0 : largestBSTHelper(root->right, &rMin, &rMax, largest);
        
        if (lCount == -1 || rCount == -1) {
            return(-1);
        } 
        
        if ((lCount == 0 || root->val >= lMax) &&
            (rCount == 0 || root->val < rMin)) {
            *min = lMin;
            *max = rMax;
            count = lCount + rCount + 1;
            *largest = myMax(*largest, count);
            return(count);
        } 
        
        return(-1);
    } 
    
    int largestBSTSubtree(struct TreeNode* root) {
        int largest = 0, min, max;
        if (root == NULL) { return(0); }
        largestBSTHelper(root, &min, &max, &largest);
        return(largest);
    }

Log in to reply
 

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