做外卖网站的模板,律师事务所 网站备案,风格活泼的网站设计,做网站和做新媒体运营文章目录 刷题前唠嗑题目#xff1a;二叉树中的伪回文路径题目描述代码与解题思路偷看大佬题解 结语 刷题前唠嗑 LeetCode#xff1f;启动#xff01;#xff01;#xff01;
这个月第一次周末早起~
题目#xff1a;二叉树中的伪回文路径
题目链接#xff1a;1457. 二… 文章目录 刷题前唠嗑题目二叉树中的伪回文路径题目描述代码与解题思路偷看大佬题解 结语 刷题前唠嗑 LeetCode启动
这个月第一次周末早起~
题目二叉树中的伪回文路径
题目链接1457. 二叉树中的伪回文路径
题目描述 代码与解题思路
func pseudoPalindromicPaths (root *TreeNode) (ans int) {cnt : make([]int, 10)dfs(root, cnt, ans)return ans
}func dfs(root *TreeNode, cnt []int, ans *int) {if root nil {return}cnt[root.Val]defer func() { cnt[root.Val]-- }()if root.Left nil root.Right nil {if isFalsePalindromes(cnt) {*ans}return}dfs(root.Left, cnt, ans)dfs(root.Right, cnt, ans)
}func isFalsePalindromes(cnt []int) bool { // 回文串最多只能存在一个奇数个数的值odd : 0for _, v : range cnt {if v%2 1 {odd}}return odd 1
}我做这道题的主要思路就是 dfs 搜索整个二叉树在搜索的过程中用一个数组记录数字的出现情况然后在走完一条路之后判断是否是伪回文串主要有两个需要注意的地方
如何判断是否是伪回文串回文串只有两种可能长度为奇数时有一个值的个数是奇数长度为偶数时每个值的个数都是奇数。也就是只要数组中的值的个数是奇数的数量 1 他就一定是伪回文串啦在使用数组进行计数的时候当 dfs 回退到上一级的时候计数需要 --不然之前的计数会影响新一条路径的计数
偷看大佬题解
func pseudoPalindromicPaths(root *TreeNode) int {return dfs(root, 0)
}func dfs(root *TreeNode, mask int) int {if root nil {return 0}mask ^ 1 root.Val // 修改 root.Val 出现次数的奇偶性if root.Left root.Right { // root 是叶子节点if mask(mask-1) 0 {return 1}return 0}return dfs(root.Left, mask) dfs(root.Right, mask)
}大佬的题解太妙了具体思路是这样的
通过 10 个二进制位来表示这个十个数字如果是值的数量是奇数则为 1如果是偶数则为 0这个是异或操作的结果通过 mask(mask-1)判断数量是奇数个的值有多少个如果存在 1 个或者 0 个使用 mask(mask-1) 操作的结果就会等于 0具体来说如果是 mask 全为 0 任何数都为零这就是存在 0 个数量的值是奇数的情况如果是 mask 有一个位是 1mask-1 这个操作会让一个 mask 中一个 1 的位置发生改变也就是如果 mask 只存在一个 1那使用 mask(mask-1) 就会等于 0。这就是存在 1 个数量的值是奇数的情况
结语
学到了位运算的新用法
