题解 | #打家劫舍(三)#

题意整理

给定一个二叉树结构的小区，每个节点都有一个房子。
现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。

方法一（递归）

1.解题思路

递归终止条件：遍历完所有节点。
递归如何传递：分别计算选与不选当前节点的情况。如果选，则加上当前节点、左孩子对应的孙子的情况，右孩子对应的孙子的情况。如果不选，则加上左孩子的最大值、右孩子的最大值。
递归的返回值：返回当前节点的最大情况。

这种方法运行会超时。

2.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int rob (TreeNode root) {
        if(root==null) return 0;
        //记录选择当前节点的可能最大金额
        int sum=root.val;
        if(root.left!=null){
            //左子节点不为空，则加上对应孙子的情况
            sum+=rob(root.left.left)+rob(root.left.right);
        }
        if(root.right!=null){
            //右子节点不为空，则加上对应孙子的情况
            sum+=rob(root.right.left)+rob(root.right.right);
        }
        //返回选与不选两种情况中的较大者
        return Math.max(sum,rob(root.left)+rob(root.right));
        
    }
}

3.复杂度分析

时间复杂度：确定某个节点最大金额时，需要访问其所有子节点，所以时间复杂度是 $O (n^{2})$ 。
空间复杂度：需要额外深度为 $l o g n$ 的递归栈，最坏情况下，退化为链表，深度为n，所以空间复杂度为 $O (n)$ 。

方法二（树形dp）

1.解题思路

状态定义：对应每一个节点， $d p [0]$ 表示选择当前节点偷到的最大可能金额， $d p [1]$ 表示不选择当前节点偷到的最大可能金额。
状态初始化：初始化为0。
状态转移：每次可以得到左右子节点的状态情况。分为选与不选当前节点两种情况。如果选，则加上当前节点值，以及两个字节点不选的状态。如果不选，则选左右孩子的最大状态，并将两者相加。

图解展示： alt

2.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int rob (TreeNode root) {
        if(root==null) return 0;
        //dp[0]表示选择当前节点的最大金额，dp[1]表示不选择当前节点的最大金额
        int[] dp=dfs(root);
        return Math.max(dp[0],dp[1]);
    }
    
    private int[] dfs(TreeNode root){
        if(root==null){
            return new int[]{0,0};
        }
        //左子节点情况
        int[] left=dfs(root.left);
        //右子节点情况
        int[] right=dfs(root.right);
        //当前节点的情况
        int[] dp=new int[2];
        //选择当前节点
        dp[0]=root.val+left[1]+right[1];
        //不选择当前节点
        dp[1]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return dp;        
        
    }
}

3.复杂度分析

时间复杂度：每次都有记录当前节点的两个状态，只需访问每个节点一次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外深度为 $l o g n$ 的递归栈，最坏情况下，退化为链表，深度为n，所以空间复杂度为 $O (n)$ 。