代码随想录二刷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 = istr[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 = 0rt := traversal(root) //还要判断下根节点是否有覆盖if rt == 0 {res++}return res
}