File tree Expand file tree Collapse file tree
Expand file tree Collapse file tree Original file line number Diff line number Diff line change 174174739. 每日温度
175175867. 转置矩阵
176176901. 股票价格跨度
177+ 968. 监控二叉树
1771781020. 飞地的数量
1781791035. 不相交的线
1791801081. 不同字符的最小子序列
Original file line number Diff line number Diff line change 4040589. N叉树的前序遍历（递归，迭代）
4141617. 合并二叉树（递归，迭代）
4242662. 二叉树最大宽度（递归，迭代）
43-
43+ 968. 监控二叉树（递归）
4444
4545二、回溯
464617. 电话号码的字母组合
Original file line number Diff line number Diff line change 1+ // 968. 监控二叉树
2+
3+
4+ /**
5+ * Definition for a binary tree node.
6+ * public class TreeNode {
7+ * int val;
8+ * TreeNode left;
9+ * TreeNode right;
10+ * TreeNode() {}
11+ * TreeNode(int val) { this.val = val; }
12+ * TreeNode(int val, TreeNode left, TreeNode right) {
13+ * this.val = val;
14+ * this.left = left;
15+ * this.right = right;
16+ * }
17+ * }
18+ */
19+
20+
21+ /*
22+ 递归
23+ 1、方法功能：入参是一个节点，返回该节点的监控状态
24+ 0：该节点无覆盖 1：该节点有摄像头 2：该节点有覆盖
25+ 2、终止条件：节点为空时，表示有覆盖，返回2
26+ 3、一个节点处理过程和返回结果：节点不为空，表示无覆盖，返回0
27+ 4、递归调用：左右节点同样需要获取监控状态，因此调用同样的方法递归处理，获取结果
28+ 5、递归顺序：后序遍历，自底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的
29+ 6、使用递归调用结果和返回结果：
30+ 1）左右节点其中一个无覆盖，那么当前节点需要安装摄像头，用于覆盖子节点，返回1
31+ 2）左右节点其中一个有摄像头，那么当前节点有覆盖，返回2
32+ 3）左右节点都有覆盖，那么当前节点无覆盖，交给当前节点的父节点处理，返回0
33+ 4）根节点无覆盖，根节点没有父节点了，要自己处理，所以要安装摄像头
34+ */
35+ class Solution {
36+ private int res = 0 ;
37+
38+ public int minCameraCover (TreeNode root ) {
39+ return dfs (root ) == 0 ? res + 1 : res ;
40+ }
41+
42+ private int dfs (TreeNode root ) {
43+ if (root == null ) {
44+ return 2 ;
45+ }
46+ int left = dfs (root .left );
47+ int right = dfs (root .right );
48+ if (left == 0 || right == 0 ) {
49+ res ++;
50+ return 1 ;
51+ }
52+ if (left == 1 || right == 1 ) {
53+ return 2 ;
54+ }
55+ return 0 ;
56+ }
57+ }
You can’t perform that action at this time.
0 commit comments