Create 337. 打家劫舍 III.md

CompetitiveLin · CompetitiveLin · commit 174b718dff6b · 2023-09-18T19:58:05.000+08:00
diff --git a/Depth First Search/337. 打家劫舍 III.md b/Depth First Search/337. 打家劫舍 III.md
@@ -0,0 +1,77 @@
+#### 337. 打家劫舍 III
+
+难度：中等
+
+---
+
+小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 `root` 。
+
+除了 `root` 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果  **两个直接相连的房子在同一天晚上被打劫**  ，房屋将自动报警。
+
+给定二叉树的 `root` 。返回 _ **在不触动警报的情况下**  ，小偷能够盗取的最高金额_ 。
+
+ **示例 1:** 
+
+![](https://assets.leetcode.com/uploads/2021/03/10/rob1-tree.jpg)
+
+```
+输入: root = [3,2,3,null,3,null,1]
+输出: 7 
+解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
+```
+
+ **示例 2:** 
+
+![](https://assets.leetcode.com/uploads/2021/03/10/rob2-tree.jpg)
+
+```
+输入: root = [3,4,5,1,3,null,1]
+输出: 9
+解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
+```
+
+ **提示：** 
+
+*   树的节点数在 `[1, 10^4]` 范围内
+*   `0 <= Node.val <= 10^4`
+
+---
+
+深度优先搜索：
+
+假设当前节点不选择，那么当前节点的最大盗取金额为左节点的最大值（不管左节点选还是不选）和右节点的最大值（同样的，不管右节点选还是不选）。
+
+递归方法的返回类型应为长度为 `2` 的数组，第一个元素表示选当前节点的最大值，第二个元素表示不选当前节点的最大值。
+
+```Java
+/**
+ * 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[] array = dfs(root);
+        return Math.max(array[0], array[1]);
+    }
+
+    private int[] dfs(TreeNode root){
+        if(root == null) return new int[]{0, 0};
+        int[] left = dfs(root.left);
+        int[] right = dfs(root.right);
+        int selected = root.val + left[1] + right[1];
+        int notSelected = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
+        return new int[]{selected, notSelected};
+    }
+}
+```
