网站服务器安全防护怎样做推广营销
题目描述
这是 LeetCode 上的 「1457. 二叉树中的伪回文路径」 ，难度为 「中等」。
Tag : 「DFS」、「位运算」
给你一棵二叉树，每个节点的值为 1 到 9 。
我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中伪回文路径的数目。
示例 1： 
输入：root = [2,3,1,3,1,null,1]
输出：2
解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。
示例 2： 
输入：root = [2,1,1,1,3,null,null,null,null,null,1]
输出：1
解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。
示例 3：
输入：root = [9]
输出：1
提示：
-
给定二叉树的节点数目在范围 内 -
DFS + 位运算
“伪回文”是指能够通过重新排列变成“真回文”，真正的回文串只有两种情况：
-
长度为偶数，即出现次数为奇数的字符个数为 个 -
长度为奇数，即出现次数为奇数的字符个数为 个（位于中间）
因此，「我们只关心路径中各个字符（数字 0-9）出现次数的奇偶性，若路径中所有字符出现次数均为偶数，或仅有一个字符出现次数为奇数，那么该路径满足要求」。
节点值范围为 ，除了使用固定大小的数组进行词频统计以外，还可以使用一个 int 类型的变量 cnt 来统计各数值的出现次数奇偶性：若 的第 位为 ，说明数值 的出现次数为奇数，否则说明数值 出现次数为偶数或没出现过，两者是等价的。
例如 代表数值 和数值 出现次数为奇数次，其余数值没出现过或出现次数为偶数次。
翻转一个二进制数字中的某一位可使用「异或」操作，具体操作位 cnt ^= 1 << k。
判断是否最多只有一个字符出现奇数次的操作，也就是判断一个二进制数字是为全为 或仅有一位 ，可配合 lowbit 来做，若 cnt 与 lowbit(cnt) = cnt & -cnt 相等，说明满足要求。
考虑到对 lowbit(x) = x & -x 不熟悉的同学，这里再做简单介绍：*lowbit(x) 表示 x 的二进制表示中最低位的 所在的位置对应的值*，即仅保留从最低位起的第一个 ，其余位均以 填充：
-
x = 6，其二进制表示为 ，那么 -
x = 12，其二进制表示为 ，那么
Java 代码：
class Solution {
int ans = 0;
public int pseudoPalindromicPaths (TreeNode root) {
dfs(root, 0);
return ans;
}
void dfs(TreeNode root, int cnt) {
if (root.left == null && root.right == null) {
cnt ^= 1 << root.val;
if (cnt == (cnt & -cnt)) ans++;
return ;
}
if (root.left != null) dfs(root.left, cnt ^ (1 << root.val));
if (root.right != null) dfs(root.right, cnt ^ (1 << root.val));
}
}
C++ 代码：
class Solution {
public:
int ans;
int pseudoPalindromicPaths(TreeNode* root) {
dfs(root, 0);
return ans;
}
void dfs(TreeNode* root, int cnt) {
if (!root->left && !root->right) {
cnt ^= 1 << root->val;
if (cnt == (cnt & -cnt)) ans++;
return;
}
if (root->left) dfs(root->left, cnt ^ (1 << root->val));
if (root->right) dfs(root->right, cnt ^ (1 << root->val));
}
};
Python 代码：
class Solution:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(root, cnt):
nonlocal ans
if not root.left and not root.right:
cnt ^= 1 << root.val
ans += 1 if cnt == (cnt & -cnt) else 0
return
if root.left:
dfs(root.left, cnt ^ (1 << root.val))
if root.right:
dfs(root.right, cnt ^ (1 << root.val))
dfs(root, 0)
return ans
TypeScript 代码：
function pseudoPalindromicPaths (root: TreeNode | null): number {
let ans = 0;
const dfs = function (root: TreeNode, cnt: number): void {
if (root.left == null && root.right == null) {
cnt ^= 1 << root.val;
if (cnt == (cnt & -cnt)) ans++;
return ;
}
if (root.left) dfs(root.left, cnt ^ (1 << root.val));
if (root.right) dfs(root.right, cnt ^ (1 << root.val));
}
dfs(root, 0);
return ans;
};
-
时间复杂度： -
空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1457 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉