題目連接：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)。
浙公網安備 33010602011771號