/**
* 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:
vector<int> graph[100010];
int vall[100010];
// memset(vall,0,sizeof(vall));
int node=1;
void run(TreeNode* root)
{
if(root==NULL) return;
int curr_par=node;
vall[node++]=root->val;
if(root->left!=NULL){ graph[curr_par].push_back(node); graph[node].push_back(curr_par); }
run(root->left);
if(root->right!=NULL){ graph[curr_par].push_back(node); graph[node].push_back(curr_par); }
run(root->right);
}
vector<int> path;
int par[100010];
int depth[100010];
void dfs(int v, int p, int d, vector<int> graph[])
{
depth[v]=d;
par[v]=p;
for(auto c:graph[v])
{
if(c!=p)
{
dfs(c,v,d+1,graph);
}
}
}
void getpath(int a, int b)
{
vector<int> path2;
path.push_back(a);
path2.push_back(b);
while(a!=b)
{
if(depth[a]<depth[b])
{
path2.push_back(b=par[b]);
}
else if(depth[a]>depth[b])
{
path.push_back(a=par[a]);
}
else if(depth[a]==depth[b])
{
path.push_back(a=par[a]);
path2.push_back(b=par[b]);
}
}
//reverse(path2.begin(),path2.end());
path2.erase(path2.begin()+int(path2.size())-1);
path.insert(path.end(),path2.begin(),path2.end());
//return path1;
}
int pseudoPalindromicPaths (TreeNode* root) {
run(root);
vector<int> leaves;
for(int i=2; i<100010; i++)
{
if(graph[i].size()==1) leaves.push_back(i);
}
dfs(1,0,0,graph);
int ans=0;
if(leaves.empty()) ans++;
for(auto x:leaves)
{
// cout<<vall[x]<<endl;
path.clear();
getpath(1,x);
int countt[10];
memset(countt,0,sizeof(countt));
for(auto x:path)
{
// cout<<x<<" ";
countt[vall[x]]++;
}
// cout<<endl;
int odd=0;
for(int i=1; i<10; i++)
{
if(countt[i])
{
if(countt[i]%2) odd++;
}
}
if(int(path.size())%2)
{
if(odd==1) ans++;
}
else
{
if(odd==0) ans++;
}
}
return ans;
}
};