深度优先遍历 DFS
解题思路
使用 后序遍历 通过递归函数的返回值来做下一步计算；
在解法一和解法二中，使用爷爷、两个孩子、4 个孙子来说明问题：爷爷选择偷，儿子就不能偷了，但是孙子可以偷，二叉树只有左右两个孩子，一个爷爷最多 2 个儿子，4 个孙子；
根据以上条件，可以得出单个节点的钱该怎么算：
- 4 个孙子的钱 + 爷爷的钱 VS 两个儿子的钱 哪个组合钱多，就当做当前节点能偷的最大钱数；这就是动态规划里面的最优子结构；
- 4 个孙子投的钱加上爷爷的钱：method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right)
- 两个儿子偷的钱：method2 = rob(root.left) + rob(root.right)
- 挑选一个钱数多的方案：result = Math.max(method1, method2)
复杂度
-
时间复杂度：
O(n^2)； -
空间复杂度：
O(logn)，算上递推系统栈的空间；
实现代码
const rob = root => {
if (root == null) return 0;
// money 为 爷爷的钱（4 个孙子的钱 + 爷爷的钱）
let money = root.val;
// 加上孙子的钱
if (root.left != null) money += (rob(root.left.left) + rob(root.left.right));
// 加上孙子的钱
if (root.right != null) money += (rob(root.right.left) + rob(root.right.right));
// rob(root.left) + rob(root.right) 为两个儿子的钱
return Math.max(money, rob(root.left) + rob(root.right));
};
记忆化搜索
解题思路
爷爷在计算自己能偷多少钱的时候，同时计算了 4 个孙子能偷多少钱，也计算了 2 个儿子能偷多少钱，这样在儿子当爷爷时，就会产生重复计算一遍孙子节点（重复子问题）；
使用备忘录把每次计算的结果都存起来，下次如果再来计算，就从缓存中取，不再计算了，这样就保证每个数字只计算一次；
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(logn)，算上递推系统栈的空间；
实现代码
const rob = root => {
// 备忘录
const memo = new Map();
return robInternal(root, memo);
};
const robInternal = (root, memo) => {
if (root == null) return 0;
// 从备忘录中取值
if (memo.has(root)) return memo.get(root);
// money 为 爷爷的钱（4 个孙子的钱 + 爷爷的钱）
let money = root.val;
// 加上孙子的钱
if (root.left != null) money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));
// 加上孙子的钱
if (root.right != null) money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));
// rob(root.left) + rob(root.right) 为两个儿子的钱
const result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));
// 存入备忘录
memo.set(root, result);
return result;
}
动态规划
解题思路
每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷；
- 当前节点选择偷时，那么两个孩子节点就不能选择偷了；
- 当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)；
确定 dp 数组以及下标的含义：使用一个大小为 2 的数组来表示， 索引 0 代表不偷，索引 1 代表偷；
确定递推公式：
- 当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱；
- 当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数；
如何初始化 dp 数组：
确定遍历顺序：后序遍历
- 通过递归左节点，得到左节点偷与不偷的金钱；
- 通过递归右节点，得到右节点偷与不偷的金钱；
举例推导 dp 数组：
复杂度
-
时间复杂度：
O(n)，每个节点只遍历了一次； -
空间复杂度：
O(logn)，算上递推系统栈的空间；
代码实现
const rob = root => {
const result = robInternal(root);
return Math.max(...result);
};
const robInternal = node => {
if (node == null) return [0, 0];
const result = new Array(2);
const left = robInternal(node.left);
const right = robInternal(node.right);
// 不偷当前节点，左右子节点都可以偷或不偷，取最大值
result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
// 偷当前节点，左右子节点只能不偷
result[1] = node.val + left[0] + right[0];
return result;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 213. 打家劫舍Ⅱ
上一篇
评论
