337. House Robber III

https://leetcode.com/problems/house-robber-iii/#/description

Analysis:

root[off] = max(root.left[off], root.left[on]) + max(root.right[off], root.right[on])

root[on] = root.left[off] + root.right[off] + root.val

do post-order traversal so that this equation gets to bubble up that yields a O(n) time complexity

Complexity:

Time: O(n)

Space: O(logn)

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int rob(TreeNode root) {
        if(root == null)
        {
            return 0;
        }
        int[] robRoot = robSub(root);
        return Math.max(robRoot[0], robRoot[1]);
    }

    private int[] robSub(TreeNode root)
    {
        if(root == null)
        {
            return new int[2];
        }

        int[] left = robSub(root.left);
        int[] right = robSub(root.right);

        int[] rootArr = new int[2];
        rootArr[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        rootArr[1] = left[0] + right[0] + root.val;

        return rootArr;
    }
}