前序遍历/二叉树/LeetCode 5418

题目链接：https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree/

• 要想排列成为回文，那么这个路径上出现过奇数次的数不能超过1个，不然无法构成回文。
• 第一个想法，用一个集合在树上记录，如果集合出现了root->val，那么就erase，否则insert，这样到最后如果集合里的元素大于1个，说明不止一个数出现了偶数次。
• 注意题目的细节：结点的值是从1~9，我们可以直接设置1至9的计数器，而不用选择集合。

class Solution {
public:
    int cnt[10];
    int ans = 0;
    void dfs(TreeNode* rt){
        if(rt == NULL) return;
        ++cnt[rt->val];
        if((!rt->left) && (!rt->right)){
            int c = 0;
            for(int i = 1;i <= 9; ++i){
                if(cnt[i] % 2) c++;
            }
            if(c <= 1) ans++;

        }else{
            dfs(rt->left);
            dfs(rt->right);
        }
        
        --cnt[rt->val]; //回溯
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        memset(cnt,0,sizeof(cnt));
        dfs(root);
        return ans;
    }
};