原题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

耗时：28min48s

C++代码

dfs、二叉树前序遍历、哈希表记录

#include<bits/stdc++.h>
using namespace std;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:map<int,int>hash;bool check(){//检查该路是否符合伪回文数int cnt = 0;for(auto it:hash){if(it.second % 2 != 0) cnt++;if(cnt>1) return false; }return true;}int pseudoPalindromicPaths (TreeNode* root) {if(root == nullptr) return 0;cout<<root->val<<" ";if(!hash.count(root->val)) hash[root->val] = 1;else hash[root->val]++;int left = pseudoPalindromicPaths(root->left);if(root->left == nullptr && root->right == nullptr){//叶子结点int flag = 0;if(check()){flag = 1;}hash[root->val]--;if(hash[root->val]== 0) hash.erase(root->val);return flag;}int right = pseudoPalindromicPaths(root->right);//回溯删除哈希表中的记录hash[root->val]--;if(hash[root->val]== 0) hash.erase(root->val);return left+right;}
};

C为check函数运行时间 n为二叉树结点个数

时间复杂度：O(C*n)

空间复杂度：O(n)

 Python代码

位运算，效率高，奇思妙想

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:ans = 0def lowbit(cnt): return cnt & -cntdef dfs(root,cnt):nonlocal ansif not root.left and not root.right:cnt ^= 1 << root.valif cnt == lowbit(cnt):ans += 1returnif root.left:dfs(root.left,cnt^(1<<root.val))if root.right:dfs(root.right,cnt^(1<<root.val))dfs(root,0)return ans