divide and conquer


  • 0
    C

    the idea is for each node we have either rob or not rob two senarios, if we store those two value for each node and recursively to solve the left and right, we can then compare which one is the greatest value. there is a catch, the max of include = left.exclude + right.exclude + root.val, however, the max exclude needs to be the max between left include and left exclude + max between right include and right exclude

    class Solution {
        class ReturnType {
            int include;
            int exclude;
            public ReturnType(int include, int exclude) {
                this.include = include;
                this.exclude = exclude;
            }
        }
        public int rob(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            ReturnType ans = divideConquer(root);
            return Math.max(ans.include, ans.exclude);
        }
        
        private ReturnType divideConquer(TreeNode root) {
            if (root == null) {
                return new ReturnType(0, 0);
            }
            
            ReturnType left = divideConquer(root.left);
            ReturnType right = divideConquer(root.right);
            
            int maxLeft = Math.max(left.include, left.exclude);
            int maxRight = Math.max(right.include, right.exclude);
            
            return new ReturnType(left.exclude + right.exclude + root.val, maxLeft + maxRight);
            
        }
    }
    
    

Log in to reply
 

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