Easy to understand Java Divide & Conquer Solution


  • 0
    C
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Pair {
        public int val;
        public boolean isValid;
        int min;
        int max;
        public Pair(int val, boolean b, int m, int n){
            this.val = val;
            this.isValid = b;
            min = m;
            max = n;
        }
    }
    public class Solution {
        int res = 0;
        int m = Integer.MAX_VALUE;
        int n = Integer.MIN_VALUE;
        public int largestBSTSubtree(TreeNode root) {
            //should be a binary search tree
            if(root == null) return 0;
            return helper(root, false).val;
        }
        private Pair helper(TreeNode root, boolean isValid) {
            if(root == null) return new Pair(0, false, m, n);
            if(root.left == null && root.right == null) return new Pair(1, true, root.val, root.val);
            
            Pair left = helper(root.left, false);
            Pair right = helper(root.right, false);
            
            Pair res = new Pair(0, false, root.val, root.val);
            
            if(root.left != null && root.right != null) {
                if(root.val > root.left.val && root.val < root.right.val && left.isValid && right.isValid && left.max < root.val && right.min > root.val) {
                    res.val = left.val + right.val + 1;
                    res.isValid = true;
                    res.max = right.max;
                    res.min = left.min;
                }else{
                    res.val = Math.max(left.val, right.val);
                    res.isValid = false;
                }
            }
            if(root.left == null) {
                if(root.val < root.right.val && right.isValid && right.min > root.val) {
                    res.val = right.val + 1;
                    res.isValid = true;
                    res.min = root.val;
                    res.max = right.max;
                }else {
                    res.val = Math.max(1, right.val);
                    res.isValid = false;
                }
            }
            if(root.right == null) {
                if(root.val > root.left.val && left.isValid && left.max < root.val) {
                    res.val = left.val + 1;
                    res.isValid = true;
                    res.max = root.val;
                    res.min = left.min;
                }else {
                    res.val = Math.max(1, left.val);
                    res.isValid = false;
                }
            }
            return res;
        }
    }

Log in to reply
 

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