Problem: 337. 打家劫舍 III
思路
题目特点： 1）输入：树 2）动态规划
解题方法
1、观察两个示例，发现小偷偷树形结构的小区，不能在相邻层偷。（注意：不是隔一层偷，我一开始的错误理解是小偷只能隔着一层偷，我容易产生固有的印象）
2、由于要一层一层去看怎么偷，则需要去遍历树。第二步，要判断遍历树的方法：前中后序和层序遍历。
通过举例子，可以排除层序遍历。
3、因为要对比下一层和上一层，且应该先计算出子树的最大值，再计算当前层的最大值，所以应使用后序遍历。
后序遍历（递归）
1、确定递归函数的参数和返回值 1）每次要记录的有两个状态：一个是偷当前节点计算得出的最大值，另一个是不偷当前节点计算得出的最大值。则返回值应使用一个数组，去保存这两个最大值。 2）参数：TreeNode root
2、确定递归函数的终止条件 1）如果你写过书店前中后序遍历，很明显：if (root == null) return [0,0];
3、确定递归函数的单层逻辑 1）分为两种情况：第一种：root==null，上面已经分析过。第二种：root != null
先计算出子树的最大值，再计算当前层的最大值
List<Integer> result = new ArrayList<>(); // 也可以用new int[2];
List<Integer> left = robTree(root.left);
List<Integer> right = robTree(root.right);
// 计算偷当前节点的最大值
int val1 = root.val + left.get(0) + right.get(0);
// 计算不偷当前节点的最大值
int val2 = Math.max(left.get(0), left.get(1)) + Math.max(right.get(0), right.get(1));
result.add(val2);
result.add(val1);
复杂度
-
时间复杂度: O(n)O(n)
-
空间复杂度: O(log2(n))O(log_2(n))【递归栈的空间】
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* 树形dp的入门题
*
* 1、确定递归函数的参数和返回值
* public List<Integer> robTree(TreeNode root)
* dp[i]的含义
* dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
*
* 2、确定终止条件
* if (root == null) return [0,0]; //伪代码
*
* 3、确定遍历顺序
* 树的后序遍历
*
* 4、确定单层递归的逻辑
* 计算偷和不偷当前节点的最大金钱
*
* @param root
* @return
*/
public int rob(TreeNode root) {
List<Integer> result = robTree(root);
return result.get(0) > result.get(1) ? result.get(0) : result.get(1);
}
/**
* 下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
* @param root
* @return
*/
public List<Integer> robTree(TreeNode root) {
List<Integer> result = new ArrayList<>();
result.add(0);
result.add(0);
if (root != null) {
// 通过递归左节点，得到左节点偷与不偷的金钱。
List<Integer> left = robTree(root.left);
// 通过递归右节点，得到右节点偷与不偷的金钱。
List<Integer> right = robTree(root.right);
int val1 = root.val + left.get(0) + right.get(0);
// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
int val2 = Math.max(left.get(0), left.get(1)) + Math.max(right.get(0), right.get(1));
// 不偷左孩子和右孩子
result.set(0, val2);
result.set(1, val1);
}
return result;
}
}