leetcode 1457. Pseudo-Palindromic Paths in a Binary Tree 二叉树中的伪回文路径

Problem: 1457. Pseudo-Palindromic Paths in a Binary Tree 二叉树中的伪回文路径

回溯，深度优先搜索，哈希表，统计每个数字的频次，当是叶子节点时，统计频次中奇数的个数，只有频数的奇数个数<=1才是伪回文串

Code

class Solution { public: vector<int> ump; int count = 0; void dfs(TreeNode* root) { if(root==nullptr) return; ump[root->val]++; if(root->left==nullptr && root->right==nullptr) { bool find = true; int cnt = 0; for(int i = 1; i < 10; i++) { if(ump[i] > 0) { if( (ump[i]&1)==1 ) cnt++; if(cnt > 1) { find = false; break; } } } if(find) count++; } dfs(root->left); dfs(root->right); ump[root->val]--; } int pseudoPalindromicPaths (TreeNode* root) { ump.assign(10, 0); dfs(root); return count; } };