題目
小偷又發現了一個新的可行竊的地區。這個地區只有一個入口，我們稱之為?root?。
除了?root?之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果?兩個直接相連的房子在同一天晚上被打劫?，房屋將自動報警。
給定二叉樹的?root?。返回?在不觸動警報的情況下?，小偷能夠盜取的最高金額?。
示例 1:
輸入: root = [3,2,3,null,3,null,1] 輸出: 7 解釋:?小偷一晚能夠盜取的最高金額 3 + 3 + 1 = 7
示例 2:
輸入: root = [3,4,5,1,3,null,1] 輸出: 9 解釋:?小偷一晚能夠盜取的最高金額 4 + 5 = 9
提示：
- 樹的節點數在?
[1, 10^4]?范圍內 0 <= Node.val <= 10^4
解答
源代碼
/*** 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) {int[] rootStatus = dfs(root);return Math.max(rootStatus[0], rootStatus[1]);}public int[] dfs(TreeNode node) {if (node == null) {return new int[]{0, 0};}int[] left = dfs(node.left);int[] right = dfs(node.right);int selected = node.val + left[1] + right[1];int notSelected = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);return new int[]{selected, notSelected};}
}總結
動態規劃，每個節點有兩種狀態，一種是當前節點被選中，一種是當前節點未被選中。當前節點被選中時，那么它的左右子節點不能被選中；當前節點未被選中時，它的左右子節點可以被選中也可以不被選中。最后得到根節點的狀態，取兩種狀態中最大的一個。
