代码随想录二刷Day37

今日任务

738.单调递增的数字
968.监控二叉树
语言：Go

738. 单调递增的数字

链接：https://leetcode.cn/problems/monotone-increasing-digits/

func monotoneIncreasingDigits(n int) int {
    tmp := strconv.Itoa(n)
    str := []byte(tmp) //要先转成byte形式，方便操作
    flag := len(str)
    for i := len(str) - 1; i > 0; i-- {
        if str[i] < str[i - 1] {
            flag = i
            str[i - 1]--;
        }
    }
    for i := flag; i < len(str); i++ {
        str[i] = '9'
    }
    res, _ := strconv.Atoi(string(str)) //将byte再转成string，方便操作
    return res
}

968. 监控二叉树

链接：https://leetcode.cn/problems/binary-tree-cameras/

1. 明确遍历方式：从叶子节点开始寻找摄像头放置位置可以保证摄像头数量最少，所以用后序遍历
2. 明确每个节点的3种状态：未被覆盖 / 有摄像头 / 被覆盖
3. 明确当前节点左右孩子的3种情况：
   左右孩子都已被覆盖，说明当前节点未被覆盖，需要增加一个摄像头；
   左右孩子至少有一个未被覆盖，说明当前节点需要增加一个摄像头，保证左右孩子都被覆盖；
   左右孩子至少有一个有摄像头，说明当前节点已被覆盖；
4. 明确根节点的状态：如果根节点未被覆盖，结果还要加1

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var res int

 //0-本节点无覆盖
 //1-本节点有摄像头
 //2-本节点有覆盖
func traversal(root *TreeNode) int {
    //空节点有覆盖
    if root == nil {
        return 2
    }

    left := traversal(root.Left) //左
    right := traversal(root.Right) //右

    //1.左右节点都有覆盖
    if left == 2 && right == 2 {
        return 0
    }

    //2.左右节点至少有一个没有被覆盖，本节点要放上摄像头
    if left == 0 || right == 0 {
        res++
        return 1
    }

    //3.左右节点至少有一个有摄像头
    if left == 1 || right == 1 {
        return 2
    }

    return -1
}

func minCameraCover(root *TreeNode) int {
    res = 0
    rt := traversal(root) //还要判断下根节点是否有覆盖
    if rt == 0 {
        res++
    }
    return res
}