---

题目1: 单调递增的数字

• 题目链接：738. 单调递增的数字

---

1- 思路

• 1. 转 String：将 int 类型的数转为 String 类型，之后通过
• 2. 逆向遍历：从后往前遍历 String
• 3. 处理思路：从 size()-2 遍历到 i >= 0
  • 处理情况：当当前元素 i 的元素值大于 后一位 i+1 ，此时需要处理
  • 处理逻辑：令 i 的元素值为当前元素值减一，同时定义 start 记录 i 的位置

---

2- 题解

⭐ 单调递增的数字——题解思路

class Solution {public int monotoneIncreasingDigits(int n) {String str = Integer.toString(n);char[] chars = str.toCharArray();int start = str.length();for (int i = str.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for(int i = start ; i<chars.length ;i++){chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}

---

题目2: 监控二叉树

• 题目链接：968. 监控二叉树

---

1- 思路

贪心思路

• 通过从下网上遍历的方式，则采取二叉树的 后序遍历 ，即 左右中方式
• 在叶子结点的上一个结点放摄像头，每隔两个结点放一个摄像头，直到遍历到根节点为止

定义结点状态

• 0 代表这个结点没覆盖
• 1 代表这个结点有摄像头
• 2 代表当前这个结点有覆盖的状态
• 空节点一定是有覆盖状态，才能满足 叶子结点的父节点是有摄像头

后续遍历逻辑

• 情况1：左右孩子都有覆盖 ——> 父节点只能是状态0，等待父节点的父节点装摄像头
• 情况2：左右孩子至少有一个无覆盖 ——> 此时 父节点 必须要装一个摄像头，只有父节点装了摄像头才能将当前结点的另一个孩子给覆盖
• 情况3：左右孩子有一个有摄像头 ——> 此时 父节点一定是覆盖状态
• 情况4：根节点无覆盖 ——> 此时 要对根节点加一个摄像头

---

2- 题解

⭐ 监控二叉树——题解思路

class Solution {int res = 0;public int minCameraCover(TreeNode root) {if(Traversal(root)==0){res++;}return res;}public int Traversal(TreeNode root){if(root== null){return 2;}int left = Traversal(root.left);int right = Traversal(root.right);// 左右孩子都覆盖if(left==2 && right==2){return 0;}// 左右至少有一个无覆盖if(left==0 || right==0){res++;return 1;}// 左右有一个摄像头，当前被覆盖if(left==1 || right==1){return 2;}return -1;}
}