C++刷leetcode（5418. 二叉树中的伪回文路径）【回溯】
题目描述：给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 1：
输入：root =
输出：2
解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 ，绿色路径 和路径 。
在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 存在回文排列 ，绿色路径 存在回文排列 。
示例 2：
输入：root =
输出：1
解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 ，路径 和路径 。
这些路径中只有绿色路径是伪回文路径，因为 存在回文排列 。
示例 3：
输入：root =
输出：1
提示：
给定二叉树的节点数目在 1 到 10^5 之间。
节点值在 1 到 9 之间
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool valid(map<int, int>&temp){
int res = 0;
for(auto cha = temp.begin(); cha != temp.end(); cha++){
if(cha -> second %2 != 0) res++;;
}
return res==1 || res == 0;
}
void dfs(TreeNode* root, int & res, map<int, int>& temp){
temp++;
if(!root->right && !root -> left){
if(valid(temp))res++;
}
if(root -> right) dfs(root -> right, res, temp);
if(root -> left) dfs(root -> left, res, temp);
temp--;
}
int pseudoPalindromicPaths (TreeNode* root) {
int res = 0;
if(root == NULL) return res;
map<int, int> temp;
dfs(root, res, temp);
return res;
}
};
注意事项：
1.使用哈希表算回文不超时。 {:10_254:}
页:
[1]