LeetCode Q250: Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Solution:

Recursion, check if subtree is univalue tree and check if root's value is as same as children's.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool helper(TreeNode* root, bool& sameToKids, int& count){
	if(root->left==NULL&&root->right==NULL){
	sameToKids=true;
	count++;
	return true;
	}
	bool sameLeft=true;
	bool sameRight=true;
	bool isLeft=true;
	bool isRight=true;
	if(root->left!=NULL)
	isLeft = helper(root->left, sameLeft, count);
	if(root->right!=NULL)
	isRight = helper(root->right, sameRight, count);
	sameToKids = (root->left==NULL? true:root->val==root->left->val)&&(root->right==NULL? true:root->val==root->right->val);
	if(sameToKids&&isLeft&&isRight){
	count++;
	return true;
	}
	}
	int countUnivalSubtrees(TreeNode* root) {
	if(root==NULL)
	return 0;
	int count=0;
	bool sameToKids;
	bool res = helper(root, sameToKids, count);
	return count;
	}
	};

view raw Q250CountUnivalueSubtrees.cpp hosted with ❤ by GitHub

Rnd3 solution:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool helper(TreeNode* root, int& count){
	if(root==NULL)
	return true;
	bool l = helper(root->left, count);
	bool r = helper(root->right, count);
	int lv = root->left==NULL? root->val:root->left->val;
	int rv = root->right==NULL? root->val:root->right->val;
	if(l&r){
	if(root->val==lv&&root->val==rv){
	count++;
	return true;
	}
	}
	return false;
	}
	int countUnivalSubtrees(TreeNode* root) {
	int count=0;
	if(root==NULL)
	return count;
	helper(root, count);
	return count;
	}
	};

view raw Q250Rnd3.cpp hosted with ❤ by GitHub