题意整理

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

方法一(递归)

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(n2)O(n^2)
  • 空间复杂度:需要额外深度为lognlogn的递归栈,最坏情况下,退化为链表,深度为n,所以空间复杂度为O(n)O(n)

方法二(树形dp)

1.解题思路

  • 状态定义:对应每一个节点,dp[0]dp[0]表示选择当前节点偷到的最大可能金额,dp[1]dp[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)O(n)
  • 空间复杂度:需要额外深度为lognlogn的递归栈,最坏情况下,退化为链表,深度为n,所以空间复杂度为O(n)O(n)