代码随想录算法训练营第三十七天| 738.单调递增的数字，968.监控二叉树

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

思路

代码

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

思路

代码

总结

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

思路

既然是求单调递增的数字，要判断相邻数字之间的大小关系。有两种遍历顺序，从前往后和从后往前。如果是从前往后，当后面的数字修改时，前面的数字可能会大于后面的数字，不满足单调递增，还要再次从前往后遍历修改。所以使用从后往前的遍历，当后面的数字小于前面的数字时，将前面的数字进行减一的操作，后面的数字改为9。例如332，2<3，则3减一变成2，后面的2变成9，329，此时2<3，继续重复上述操作变成299，得到最后结果。

代码

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum =
            to_string(n); // 为了方便处理每一位上的数字，将其转换成字符串
        int flag = strNum.size(); // 用来标记从哪一位开始后面的数字改成9
        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); // 将字符串转换成int型整数返回
    }
};

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

思路

一个摄像头可以监控上中下三层，为了使用更少的摄像头，我们尽可能把摄像头放在中间。对于二叉树首先要确定遍历顺序，因为叶子比根节点多，所以使用后序遍历，从叶子节点开始遍历，先满足大多数节点摄像头数量最少。

其次，既然求最少的摄像头数量，就要明确每个节点到底是什么状态，其实状态无外乎三种：没被监控覆盖0，有摄像头1，被监控覆盖2。

然后就是处理逻辑，也有以下几种情况

①孩子节点都为2，则父节点没被覆盖，返回0

②有一个孩子为0，则父节点需要放摄像头，返回1

③有一个孩子为1，则父节点被覆盖，返回2

④根节点没被覆盖，递归到根节点结束，无法赋值状态，所以单独处理

需要注意的点，空节点的处理，遇到空节点应该返回2，被覆盖，不影响最终摄像头的数量

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    // 节点状态
    // 有摄像头1，被监控覆盖2，没被监控覆盖0
    int result = 0; // 记录摄像头个数
    // 递归遍历二叉树
    int traversal(TreeNode* cur) {
        if (cur == NULL)
            return 2; // 空节点返回2
        // 后序遍历，左右中
        int left = traversal(cur->left);
        int right = traversal(cur->right);
        // 四种情况
        // 1.孩子节点都为2，则父节点没被覆盖，返回0
        // 2.有一个孩子为0，则父节点需要放摄像头，返回1
        // 3.有一个孩子为1，则父节点被覆盖，返回2
        // 4.根节点没被覆盖，递归到根节点结束，无法赋值状态，所以单独处理
        if (left == 2 && right == 2)
            return 0; // 情况1
        if (left == 0 || right == 0) {
            result++;
            return 1; // 情况2
        }
        if (left == 1 || right == 1)
            return 2; // 情况3
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        if (root == NULL)
            return result;
        if (traversal(root) == 0)
            result++; // 情况4
        return result;
    }
};