随机算法训练营第 37 天|LeetCode738 单调递增数，LeetCode968 监控二叉树

738.单调递增的数字

思路：要求一个数字从第一位往后的大小是单调递增的，先把数字转换成字符串，然后从后往前逐位遍历，如果当前位比前一位小，则前一位--，从当前位往后都应该为9，因此记下当前位置。

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

    }
};

968.监控二叉树 

思路：从叶子节点往上安装摄像头，节点分为三种状态，0无覆盖，1摄像头，2有覆盖，当节点为空，返回2有覆盖。后序遍历，将节点的状态返回给上一层，上一层再根据子节点的状态返回自己的状态。每当return1时，result++，如果根节点返回0，说明根节点还需要放一个摄像头，result再++。

class Solution {
public:
int result = 0;
    int traversal(TreeNode*root)
    {
        //0无覆盖
        //1摄像头
        //2有覆盖
        if(root ==NULL)
        {
            return 2;
        }
        int left = traversal(root->left);
        int right = traversal(root->right);
        //左右为2
        if(left==2&&right==2)
        {
            return 0;
        }
        else if(right==0||left==0)
        {
            result++;
            return 1;
        }
        else if(left ==1||right==1)
        {
            return 2;
        }
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        if(traversal(root)==0)
        {
            result++;
        }
        return result;

    }
};