目录

LeeCode 738.单调递增的数字

LeeCode 968.监控二叉树

---

LeeCode 738.单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

思路：从后向前遍历，遇到strNum[i - 1] > strNum[i]的情况，则strNum[i - 1]--；，重复利用上次比较的结果进行比较，直至得出最终答案。

时间复杂度：O（n）                        空间复杂度：O（n）

class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--) {if (strNum[i - 1] > strNum[i]) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

---

LeeCode 968.监控二叉树

968. 监控二叉树 - 力扣（LeetCode）

思路：使用后序遍历从下往上每隔两个节点放一个摄像头。

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量最少。

状态转移：0：该节点无覆盖；   1：本节点有摄像头；   2：本节点有覆盖。

时间复杂度：O（n）                        空间复杂度：O（n） 

class Solution {
private:int result;int traversal(TreeNode* cur) {if (cur == NULL) return 2;int left = traversal(cur->left);int right = traversal(cur->right);if (left == 2 && right == 2)  return 0;if (left == 0 || right == 0) {result++;return 1;}if (left == 1 || right == 1) return 2;return -1;}
public:int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) result++;return result;}
};