337. 打家劫舍III

动态规划

class Solution {
    public int rob(TreeNode root) {

        int[] dp = robOrNot(root);

        return Math.max(dp[0], dp[1]);
    }

    /**
     * 对于每个节点来说，都有选择和不选择偷两种选择
     * 对每个节点定义一个数组，dp[0]表示不偷该节点时的最大金额，此时两个孩子都可以选择偷或者不偷，即dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
     * dp[1]表示偷该节点，此时两个孩子都不能偷，即dp[1] = root.val + left[0] + right[0]
     * 二者取最大值就是在该节点能偷的最大金额
     */
    public int[] robOrNot(TreeNode root){

        int[] dp = new int[2];

        /**
         * 如果是空节点，无论偷不偷都是0
         */
        if (root == null){
            return dp;
        }

        /**
         * 后序遍历，从后往前记录每个节点偷与不偷的最大金额
         */
        int[] left = robOrNot(root.left);
        int[] right = robOrNot(root.right);

        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        dp[1] = root.val + left[0] + right[0];

        return dp;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(logn)
 */

https://leetcode-cn.com/problems/house-robber-iii/