题目连接：337. 打家劫舍 III - 力扣（LeetCode）
题目分析：
二叉树的后续遍历，dp[root] 表示 root节点的最大收益
dp[root] = max(dp[root.left] + dp[root.right], root.val + dp[root.left.left] + dp[root.left.right] + dp[root.right.left] + dp[root.right.right])
我们可以在原始的二叉树上进行记录，因为题目中没有说不允许改变二叉树的内容；
我们使用二叉树的后续遍历，当前节点的最大收益为取当前节点，和不取当前节点的最大值，不取当前节点的话那就是两个子数的根节点
的值之和，如果取当前节点的话，由于不能相邻的节点一起偷，所以这时候其收益为当前节点的数值加上左节点的左右节点的数值和右节
点的左右节点数值之和（如果他们存在的话）
代码实现如下：
/**
* 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 {
public int rob(TreeNode root) {
// 二叉树的后续遍历，dp[root] 表示 root节点的最大收益
// dp[root] = max(dp[root.left] + dp[root.right],
// root.val + dp[root.left.left] + dp[root.left.right] + dp[root.right.left] + dp[root.right.right])
dfs(root);
return root.val;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
root.val = Math.max(
(root.left == null ? 0:root.left.val) +
(root.right == null? 0:root.right.val),
root.val +
(root.left == null? 0: (root.left.left == null ? 0: root.left.left.val)) +
(root.left == null? 0: (root.left.right == null ? 0: root.left.right.val)) +
(root.right == null? 0: (root.right.left == null ? 0: root.right.left.val)) +
(root.right == null? 0: (root.right.right == null ? 0: root.right.right.val))
);
}
}
复杂度分析：时间复杂度 O(n)
空间复杂度：O(n)
递归实现的本质也是系统帮我们建立了栈结构，而系统栈需要记住每个节点的值，所以空间复杂度仍为O(n)。
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
