//Step 1: Understand problem
//we want to check first if a subtree is Univalue or not
//Finding such univalue subtree and counting total no of nodes
//in all such uni subtrees gives our answer
//Step2: Algorithm
//we use DFS to traverse to leaf nodes, basically
//for every sub/root we want to check that if that subtree
//is Uni or not.
//At every instace, basically we will have the left child and right
//child of that sub root, then only we proceed to IF Statments
//if both l and r TRUE, meaning we good till l subtree and r subtree
//and just wanna check for the root of l n r
bool isUni(BinaryTreeNode<int>* root, int &count){
if(root==NULL) return true;
bool l = isUni(root->left, count);
bool r = isUni(root->right, count);
if(l && r){
if(root->left != NULL && root->data != root->left->data ||
root->right != NULL && root->data != root->right->data){
return false;
}
count++;
return true;
}
else return false;
}
int countUnivalTrees(BinaryTreeNode<int> *root)
{
int count = 0;
isUni(root, count);
return count;
}