C++刷leetcode（5418. 二叉树中的伪回文路径）【回溯】

糖逗

题目描述：

1. 给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
   
2. 
   
3. 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
   
4. 
   
5.  
   
6. 
   
7. 示例 1：
   
8. 
   
9. 
   
10. 
    
11. 输入：root = [2,3,1,3,1,null,1]
    
12. 输出：2
    
13. 解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
    
14.      在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。
    
15. 示例 2：
    
16. 
    
17. 
    
18. 
    
19. 输入：root = [2,1,1,1,3,null,null,null,null,null,1]
    
20. 输出：1
    
21. 解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
    
22.      这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。
    
23. 示例 3：
    
24. 
    
25. 输入：root = [9]
    
26. 输出：1
    
27.  
    
28. 
    
29. 提示：
    
30. 
    
31. 给定二叉树的节点数目在 1 到 10^5 之间。
    
32. 节点值在 1 到 9 之间
    
33. 
    
34. 来源：力扣（LeetCode）
    
35. 链接：https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree
    
36. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
   
10. * };
    
11. */
    
12. class Solution {
    
13. public:
    
14.     bool valid(map<int, int>&temp){
    
15.         int res = 0;
    
16.         for(auto cha = temp.begin(); cha != temp.end(); cha++){
    
17.             if(cha -> second %2 != 0) res++;;
    
18.         }
    
19.         return res==1 || res == 0;
    
20.     }
    
21.     void dfs(TreeNode* root, int & res, map<int, int>& temp){
    
22.         temp[root -> val]++;
    
23.         if(!root->right && !root -> left){
    
24.             if(valid(temp))res++;
    
25.         }
    
26.         if(root -> right) dfs(root -> right, res, temp);
    
27.         if(root -> left) dfs(root -> left, res, temp);
    
28.         temp[root ->val]--;
    
29.     }
    
30. 
    
31.     int pseudoPalindromicPaths (TreeNode* root) {
    
32.         int res = 0;
    
33.         if(root == NULL) return res;
    
34.         map<int, int> temp;
    
35.         dfs(root, res, temp);
    
36.         return res;
    
37.     }
    
38. };

复制代码

注意事项：
1.使用哈希表算回文不超时。

糖逗