Given a binary tree, count the number of Single Valued Subtrees. A Single Valued Subtree is one in which all the nodes have same value. 
Example 1
Input :
              5
             / \
            1   5
           / \   \
          5   5   5
Output : 4
Explanation : 
There are 4 subtrees with single values. Three leaf nodes and the subtree whose root is the right child of the root. 
Example 2:
Input:
              5
             / \
            4   5
           / \   \
          4   4   5   
Output: 5
Explanation: 
There are five subtrees with single values.
Your task :
You don't have to read input or print anything. Your task is to complete the function singlevalued() which takes the root of the tree as input and returns the count of single valued subtrees.
 
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(n)
 
Constraints :
1 <= n <= 10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



class Solution:

    def singlevalued(self, root):

        #code here

Solutions:
class Solution:

	def util(self, root):
		global count
		if root == None:
			return [1, None]
		if root.left == None and root.right == None:
			count += 1
			return [1, root.data]
		l = self.util(root.left)
		r = self.util(root.right)
		if l[0] == 1 and r[0] == 1:
			if l[1] == None and r[1] == None:
				return [1, root.data]
			elif l[1] == None and r[1] == root.data:
				count += 1
				return [1, root.data]
			elif r[1] == None and l[1] == root.data:
				count += 1
				return [1, root.data]
			elif l[1] == r[1] and l[1] == root.data:
				count += 1
				return [1, root.data]
			else:
				return [0, root.data]
		else:
			return [0, root.data]

	def singlevalued(self, root):
		global count
		count = 0
		self.util(root)
		return count


class Solution:

	def singlevalued(self, root):
		c = [0] * 1

		def fun(root):
			if root == None:
				return True
			l = fun(root.left)
			r = fun(root.right)
			cur = root.data
			if root.left:
				left = root.left.data
			else:
				left = cur
			if root.right:
				right = root.right.data
			else:
				right = cur
			if cur == left and cur == right and l and r:
				c[0] += 1
				return True
			return False
		fun(root)
		return c[0]


class Solution:

	def singlevalued(self, root):
		count = [0]

		def answer(root):
			if root == None:
				return set()
			lset = answer(root.left)
			rset = answer(root.right)
			lset.add(root.data)
			lset.update(rset)
			if len(lset) == 1:
				count[0] += 1
			return lset
		answer(root)
		return count[0]


class Solution:

	def postOrder(self, root, count):
		if root is None:
			return True
		left = self.postOrder(root.left, count)
		right = self.postOrder(root.right, count)
		if left == False or right == False:
			return False
		if root.left and root.data != root.left.data or (root.right and root.data != root.right.data):
			return False
		count[0] += 1
		return True

	def singlevalued(self, root):
		count = [0]
		self.postOrder(root, count)
		return count[0]


class Solution:

	def solve(self, root):
		if root == None:
			return True
		l = self.solve(root.left)
		r = self.solve(root.right)
		cur = root.data
		if root.left:
			left = root.left.data
		else:
			left = cur
		if root.right:
			right = root.right.data
		else:
			right = cur
		if cur == left and cur == right and l and r:
			self.count += 1
			return True
		return False

	def singlevalued(self, root):
		self.count = 0
		self.s = set()
		self.solve(root)
		return self.count


class Solution:
	c = 0

	def finder(self, root):
		if root == None:
			return 1
		lef = self.finder(root.left)
		righ = self.finder(root.right)
		if lef == False or righ == False:
			return 0
		if root.left != None and root.data != root.left.data:
			return 0
		if root.right != None and root.data != root.right.data:
			return 0
		self.c += 1
		return 1

	def singlevalued(self, root):
		self.finder(root)
		return self.c


class Solution:

	def singlevalued(self, root):
		self.ans = 0

		def dfs(node):
			if not node.left and (not node.right):
				self.ans += 1
				return node.data
			if node.left and node.right:
				left = dfs(node.left)
				right = dfs(node.right)
				if node.data == left and node.data == right:
					self.ans += 1
					return node.data
			elif node.left:
				left = dfs(node.left)
				if node.data == left:
					self.ans += 1
					return node.data
			elif node.right:
				right = dfs(node.right)
				if node.data == right:
					self.ans += 1
					return node.data
			return float('inf')
		dfs(root)
		return self.ans


class Solution:

	def singlevalued(self, root):
		c = 0

		def check(n):
			nonlocal c
			if n.left == None and n.right == None:
				c += 1
				return True
			if n.left != None:
				l = check(n.left)
			else:
				l = True
			if n.right != None:
				r = check(n.right)
			else:
				r = True
			if l == True and r == True:
				if n.left != None and n.right != None:
					if n.data == n.left.data and n.data == n.right.data:
						c += 1
						return True
					if n.data != n.left.data or n.data != n.right.data:
						return False
				if n.left == None and n.right != None:
					if n.data == n.right.data:
						c += 1
						return True
					else:
						return False
				if n.left != None and n.right == None:
					if n.data == n.left.data:
						c += 1
						return True
					else:
						return False
		check(root)
		return c


class Solution:

	def findSingleValued(self, root, count):
		if root == None:
			return True
		if root.left == None and root.right == None:
			count[0] += 1
			return True
		left = 1
		right = 1
		if root.left:
			left = self.findSingleValued(root.left, count)
		if root.right:
			right = self.findSingleValued(root.right, count)
		if left and right:
			temp = []
			temp.append(root.data)
			if root.left:
				temp.append(root.left.data)
			if root.right:
				temp.append(root.right.data)
			first = temp[0]
			for i in range(1, len(temp)):
				if temp[i] != first:
					return False
			count[0] += 1
			return True
		return False

	def singlevalued(self, root):
		count = [0]
		self.findSingleValued(root, count)
		return count[0]


class Solution:

	def singlevalued(self, root):

		def check(root):
			if root.left == None and root.right == None:
				return True
			if root.left:
				if root.right:
					if root.data == root.left.data and root.data == root.right.data:
						return check(root.right) and check(root.left)
					else:
						return False
				elif root.data == root.left.data:
					return check(root.left)
				else:
					return False
			elif root.right:
				if root.left == None:
					if root.data == root.right.data:
						return check(root.right)
					else:
						return False

		def traverse(root):
			if check(root):
				c[0] += 1
			if root == None:
				return
			if root.left:
				traverse(root.left)
			if root.right:
				traverse(root.right)
		c = [0]
		traverse(root)
		return c[0]


class Solution:
	ans = 0

	def check(self, root):
		if root is None:
			return True
		lhs = self.check(root.left)
		rhs = self.check(root.right)
		if lhs and rhs:
			if root.left is not None and root.left.data != root.data:
				return False
			if root.right is not None and root.right.data != root.data:
				return False
			self.ans = self.ans + 1
			return True
		return False

	def singlevalued(self, root):
		self.check(root)
		return self.ans


class Solution:

	def singlevalued(self, root):
		self.ans = 0

		def solve(root):
			if root == None:
				return True
			l = solve(root.left)
			r = solve(root.right)
			if l == False or r == False:
				return False
			elif root.left and root.left.data != root.data:
				return False
			elif root.right and root.right.data != root.data:
				return False
			else:
				self.ans += 1
				return True
		val = solve(root)
		return self.ans


class Solution:

	def Postorder(self, root, dict):
		if root == None:
			return 0
		l = self.Postorder(root.left, dict)
		r = self.Postorder(root.right, dict)
		if root.left == None and root.right == None:
			if root.data not in dict:
				dict[root.data] = 1
			else:
				dict[root.data] += 1
			return root.data
		if l != 0 and r != 0:
			if l == r and l == root.data:
				if root.data not in dict:
					dict[root.data] = 1
				else:
					dict[root.data] += 1
				return root.data
		elif l != 0:
			if l == root.data:
				if root.data not in dict:
					dict[root.data] = 1
				else:
					dict[root.data] += 1
				return root.data
		elif r != 0:
			if r == root.data:
				if root.data not in dict:
					dict[root.data] = 1
				else:
					dict[root.data] += 1
				return root.data
		return -1

	def singlevalued(self, root):
		dict = {}
		self.Postorder(root, dict)
		ans = 0
		for key in dict:
			ans += dict[key]
		return ans


class Solution:

	def singlevalued(self, root):
		count = 0

		def f(root):
			if not root:
				return (True, 0)
			if root:
				if root.left and root.right:
					(left, total_l) = f(root.left)
					(right, total_r) = f(root.right)
					if root.data == root.left.data and root.data == root.right.data and left and right:
						return (True, 1 + total_l + total_r)
					else:
						return (False, total_l + total_r)
				elif root.left and (not root.right):
					(left, total_l) = f(root.left)
					if root.data == root.left.data and left:
						return (True, 1 + total_l)
					else:
						return (False, total_l)
				elif not root.left and root.right:
					(right, total_r) = f(root.right)
					if root.data == root.right.data and right:
						return (True, 1 + total_r)
					else:
						return (False, total_r)
				elif not root.left and (not root.right):
					return (True, 1)
		return f(root)[1]


class Solution:

	def solve(self, root, res):
		if root.left is None and root.right is None:
			return (root.data, res + 1)
		(left, right) = (root.data, root.data)
		if root.left:
			(left, res) = self.solve(root.left, res)
		if root.right:
			(right, res) = self.solve(root.right, res)
		if left == right and left == root.data:
			return (root.data, res + 1)
		return (-1, res)

	def singlevalued(self, root):
		return self.solve(root, 0)[1]


class Solution:

	def singlevalued(self, root):
		self.ans = 0
		self.helper(root)
		return self.ans

	def helper(self, root):
		if root == None:
			return True
		left = self.helper(root.left)
		right = self.helper(root.right)
		if left and right:
			if root.left != None and root.left.data != root.data:
				return False
			if root.right != None and root.right.data != root.data:
				return False
			self.ans += 1
			return True
		return False


class Solution:

	def singlevalued(self, root):

		def f(root, ans):
			if not root:
				return -1
			if not root.left and (not root.right):
				ans[0] += 1
				return root.data
			l = f(root.left, ans)
			r = f(root.right, ans)
			if l == root.data and r == root.data or (l == -1 and r == root.data) or (r == -1 and l == root.data):
				ans[0] += 1
				return root.data
			return 0
		ans = [0]
		res = f(root, ans)
		return ans[0]


class Solution:

	def singlevalued(self, root):
		return self.helper(root)[1]

	def helper(self, root):
		if root is None:
			return ([], 0)
		(left, l_count) = self.helper(root.left)
		(right, r_count) = self.helper(root.right)
		current = (left == [] or left == [root.data]) and (right == [] or right == [root.data])
		count = l_count + r_count + current
		nodes = left + right + [root.data]
		if current:
			nodes = [root.data]
		return (nodes, count)


g = None

def f(p):
	global g
	pass
	ok = True
	l = p.left
	r = p.right
	if l:
		ok = f(l) and l.data == p.data and ok
	if r:
		ok = f(r) and r.data == p.data and ok
	if ok:
		g += 1
	return ok

class Solution:

	def singlevalued(self, root):
		global g
		if not root:
			return 0
		g = 0
		f(root)
		return g


class Solution:

	def singlevalued(self, root):

		def helper(root, count):
			if root is None:
				return True
			leftSide = helper(root.left, count)
			rightSide = helper(root.right, count)
			if leftSide and rightSide and (True if root.left is None else root.left.data == root.data) and (True if root.right is None else root.right.data == root.data):
				count[0] += 1
				return True
			else:
				return False
		count = [0]
		helper(root, count)
		return count[0]


class Solution:

	def singlevalued(self, root):
		c = [0]

		def solve(root):
			if root == None:
				return (0, True)
			if not root.left and (not root.right):
				c[0] += 1
				return (root.data, True)
			(data1, bool1) = solve(root.left)
			(data2, bool2) = solve(root.right)
			if (root.data == data1 and root.data == data2 or (data1 == 0 and root.data == data2) or (root.data == data1 and data2 == 0)) and (bool1 and bool2):
				c[0] += 1
				return (root.data, bool1 and bool2)
			else:
				return (-1, False)
		(v, v1) = solve(root)
		return c[0]


class Solution:

	def singlevalued(self, root):
		count = [0]

		def value(root):
			if not root:
				return (0, True)
			if not root.left and (not root.right):
				count[0] += 1
				return (root.data, True)
			(data1, boo1) = value(root.left)
			(data2, boo2) = value(root.right)
			if (root.data == data1 and root.data == data2 or (data1 == 0 and root.data == data2 or (root.data == data1 and data2 == 0))) and (boo1 and boo2):
				count[0] += 1
				return (root.data, boo1 and boo2)
			else:
				return (-1, False)
		(v, v1) = value(root)
		return count[0]


class Solution:

	def singlevalued(self, root):
		self.count = 0

		def solve(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				self.count += 1
				return True
			l = solve(root.left)
			r = solve(root.right)
			if l and r:
				if root.data == root.left.data and root.data == root.right.data:
					self.count += 1
					return True
				else:
					return False
			elif root.left == None and root.right != None:
				if r == True:
					if root.data == root.right.data:
						self.count += 1
						return True
			elif root.right == None and root.left != None:
				if l == True:
					if root.data == root.left.data:
						self.count += 1
						return True
			else:
				return False
		solve(root)
		return self.count


class Solution:

	def singlevalued(self, root):
		(bol, val, ct) = self.recursive(root)
		return ct

	def recursive(self, root):
		if root is None:
			return (True, None, 0)
		(rt_bool, rt_val, rt_ct) = self.recursive(root.right)
		(lt_bool, lt_val, lt_ct) = self.recursive(root.left)
		if (rt_bool and lt_bool) and (rt_val is None or rt_val == root.data) and (lt_val is None or lt_val == root.data):
			return (True, root.data, lt_ct + rt_ct + 1)
		else:
			return (False, root.data, lt_ct + rt_ct)


from collections import namedtuple
Result = namedtuple('Result', 'valid,cnt')

class Solution:

	def singlevalued(self, root):
		ans = [0]
		dfs(root, ans)
		return ans[0]

def dfs(n, ans):
	if not n:
		return True
	l = dfs(n.left, ans)
	r = dfs(n.right, ans)
	if not l or not r:
		return False
	if n.left and n.left.data != n.data:
		return False
	if n.right and n.right.data != n.data:
		return False
	ans[0] += 1
	return True


class Solution:
	count = 0

	def singlevalued(self, root):
		self.dfs(root)
		return self.count

	def dfs(self, root):
		if root:
			a = self.dfs(root.left)
			b = self.dfs(root.right)
			if a == -1 and b == -1 or (a == -1 and b == root.data) or (b == -1 and a == root.data):
				self.count += 1
				return root.data
			if a == b == root.data:
				self.count += 1
				return root.data
			return float('-inf')
		return -1


class Solution:
	count = 0

	def checkSingle(self, root):
		if root == None:
			return True
		rightBool = self.checkSingle(root.right)
		leftBool = self.checkSingle(root.left)
		if leftBool is False or rightBool is False:
			return False
		if root.right != None and root.right.data != root.data:
			return False
		if root.left != None and root.left.data != root.data:
			return False
		self.count += 1
		return True

	def singlevalued(self, root):
		self.checkSingle(root)
		return self.count


class Solution:

	def singlevalued(self, root):
		global cnt
		cnt = 0
		self.traverse(root)
		return cnt

	def traverse(self, root):
		global cnt
		if not root:
			return False
		if not root.right and (not root.left):
			cnt += 1
			return True
		x = self.traverse(root.left)
		y = self.traverse(root.right)
		if x and y:
			if root.right.data == root.data and root.left.data == root.data:
				cnt += 1
				return True
		elif root.left is None:
			if y and root.right.data == root.data:
				cnt += 1
				return True
		elif root.right is None:
			if x and root.left.data == root.data:
				cnt += 1
				return True
		return False


class Solution:

	def singlevalued(self, root):
		global cnt
		cnt = 0
		list = self.traverse(root)
		if len(set(list)) == 1:
			cnt += 1
		return cnt

	def traverse(self, root):
		global cnt
		if not root:
			return []
		x = self.traverse(root.left)
		y = self.traverse(root.right)
		if x and x[0] != -1 and (len(set(x)) == 1):
			cnt += 1
			x = [x[0]]
		elif x:
			x = [-1]
		if y and y[0] != -1 and (len(set(y)) == 1):
			cnt += 1
			y = [y[0]]
		elif y:
			y = [-1]
		return [root.data] + x + y


class Solution:

	def getCounts(self, node):
		if node is None:
			return (None, 0)
		(val1, cnt1) = self.getCounts(node.left)
		(val2, cnt2) = self.getCounts(node.right)
		cnt = cnt1 + cnt2
		if (val1 is None or val1 == node.data) and (val2 is None or val2 == node.data):
			cnt += 1
			return (node.data, cnt)
		return (False, cnt)

	def singlevalued(self, root):
		(_, cnt) = self.getCounts(root)
		return cnt


class Solution:

	def singlevalued(self, root):
		singleValue = [0]

		def Walker(node: Node):
			if node.data is None:
				return float('inf')
			if node.left is not None:
				left = Walker(node.left)
			else:
				left = node.data
			if node.right is not None:
				right = Walker(node.right)
			else:
				right = node.data
			if node.data == left == right:
				singleValue[0] = singleValue[0] + 1
				return node.data
			return float('inf')
		Walker(root)
		return singleValue[0]


class Solution:

	def singlevalued(self, root):

		def traversal(root):
			nonlocal count
			if root == None:
				return None
			if root.left:
				traversal(root.left)
			if root.right:
				traversal(root.right)
			if root.left and root.right:
				if root.left.data == root.right.data == root.data:
					count += 1
				elif root.left.data == root.right.data and root.left.data != root.data:
					root.data = -9999999
				elif root.left.data != root.data:
					root.data = root.left.data
			elif root.left:
				if root.left.data == root.data:
					count += 1
				else:
					root.data = -999999999
			elif root.right:
				if root.right.data == root.data:
					count += 1
				else:
					root.data = -11111111
			elif root.left == None and root.right == None:
				count += 1
		count = 0
		traversal(root)
		return count


def solve(node, ans):
	if node is None:
		return (True, 'x')
	left = solve(node.left, ans)
	right = solve(node.right, ans)
	if (left[0] and right[0]) and (left[1] == 'x' or left[1] == node.data) and (right[1] == 'x' or right[1] == node.data):
		ans[0] += 1
		return (True, node.data)
	return (False, node.data)

class Solution:

	def singlevalued(self, root):
		ans = [0]
		solve(root, ans)
		return ans[0]


class Solution:

	def helper(self, root, count):
		if not root:
			return True
		left = self.helper(root.left, count)
		right = self.helper(root.right, count)
		if left == False or right == False:
			return False
		if root.left and root.data != root.left.data:
			return False
		if root.right and root.data != root.right.data:
			return False
		count[0] += 1
		return True

	def singlevalued(self, root):
		count = [0]
		self.helper(root, count)
		return count[0]


class Solution:

	def helper(self, root):
		if not root.left and (not root.right):
			self.count += 1
			return (True, root.data)
		(rflag, rval, lflag, lval) = (True, root.data, True, root.data)
		if root.left:
			(lflag, lval) = self.helper(root.left)
		if root.right:
			(rflag, rval) = self.helper(root.right)
		if lflag and rflag and (lval == rval) and (root.data == lval) and (root.data == rval):
			self.count += 1
			return (True, root.data)
		return (False, root.data)

	def singlevalued(self, root):
		self.count = 0
		self.helper(root)
		return self.count


import sys

class Solution:

	def dfs(self, root, c):
		if root is None:
			return True
		left = self.dfs(root.left, c)
		right = self.dfs(root.right, c)
		if left == False or right == False:
			return False
		if root.left and root.data != root.left.data:
			return False
		if root.right and root.data != root.right.data:
			return False
		c[0] += 1
		return True

	def singlevalued(self, root):
		c = [0]
		self.dfs(root, c)
		return c[0]


class Solution:

	def singlevalued(self, root):
		count = [0]

		def traverse(root, count):
			if not root:
				return True
			l_tree = traverse(root.left, count)
			r_tree = traverse(root.right, count)
			if l_tree == False or r_tree == False:
				return False
			if root.left and root.data != root.left.data or (root.right and root.data != root.right.data):
				return False
			count[0] += 1
			return True
		traverse(root, count)
		return count[0]


class Solution:

	def singlevalued(self, root):
		s = 0
		nodes = [[root, 0, True]]
		while len(nodes) > 0:
			(node, status, isSVST) = nodes[-1]
			if status == 0:
				if node.left is not None:
					nodes[-1][1] = 1
					nodes[-1][2] = node.data == node.left.data
					nodes.append([node.left, 0, True])
				elif node.right is not None:
					nodes[-1][1] = 2
					nodes[-1][2] = isSVST and node.data == node.right.data
					nodes.append([node.right, 0, True])
				else:
					s += 1
					nodes.pop()
			elif status == 2 or (status == 1 and node.right is None):
				if isSVST:
					s += 1
				nodes.pop()
				if len(nodes) > 0:
					nodes[-1][2] = isSVST and nodes[-1][2]
			else:
				nodes[-1][1] = 2
				nodes[-1][2] = isSVST and node.data == node.right.data
				nodes.append([node.right, 0, True])
		return s


class Solution:

	def postord(self, root, cnt):
		if root != None:
			(lft, cnt) = self.postord(root.left, cnt)
			(rght, cnt) = self.postord(root.right, cnt)
			if lft != 'T' or rght != 'T':
				return ('F', cnt)
			if root.left != None and root.left.data != root.data:
				return ('F', cnt)
			if root.right != None and root.right.data != root.data:
				return ('F', cnt)
			cnt += 1
			return ('T', cnt)
		else:
			return ('T', cnt)

	def singlevalued(self, root):
		cnt = 0
		if root != None:
			(value, cnt) = self.postord(root, cnt)
		return cnt


class Solution:

	def singlevalued(self, root):
		res = 0

		def helper(node):
			nonlocal res
			if not node:
				return None
			left = helper(node.left)
			right = helper(node.right)
			if not node.left and (not node.right):
				res += 1
				return node.data
			elif not node.left and right == node.data:
				res += 1
				return node.data
			elif not node.right and left == node.data:
				res += 1
				return node.data
			elif node.left and node.right and (left == right == node.data):
				res += 1
				return node.data
			return None
		helper(root)
		return res


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

class Solution:

	def countSingleRec(self, root, count):
		if root is None:
			return True
		left = self.countSingleRec(root.left, count)
		right = self.countSingleRec(root.right, count)
		if left == False or right == False:
			return False
		if root.left and root.data != root.left.data:
			return False
		if root.right and root.data != root.right.data:
			return False
		count[0] += 1
		return True

	def singlevalued(self, root):
		count = [0]
		self.countSingleRec(root, count)
		return count[0]


def f(temp, ans):
	if temp is None:
		return True
	a = f(temp.left, ans)
	b = f(temp.right, ans)
	if a and b:
		if temp.left is not None and temp.left.data != temp.data:
			return False
		if temp.right is not None and temp.right.data != temp.data:
			return False
		ans[0] += 1
		return True
	return False

class Solution:

	def singlevalued(self, root):
		ans = [0]
		f(root, ans)
		return ans[0]


import math

class Solution:

	def solve(self, root):
		left = root.data
		if root.left:
			left = self.solve(root.left)
		right = root.data
		if root.right:
			right = self.solve(root.right)
		if left == right == root.data:
			self.ans += 1
			return root.data
		return None

	def singlevalued(self, root):
		self.ans = 0
		self.solve(root)
		return self.ans


class Solution:

	def singlevalued(self, root):
		cnt = 0

		def sol(root):
			nonlocal cnt
			if not root:
				return True
			lf = sol(root.left)
			rf = sol(root.right)
			if lf and rf:
				x = root.left is None or root.left.data == root.data
				y = root.right is None or root.right.data == root.data
				if x and y:
					cnt += 1
					return True
			return False
		sol(root)
		return cnt


class Solution:

	def __init__(self):
		self.res = 0

	def singlevalued(self, root):
		self.dfs(root)
		return self.res

	def dfs(self, node):
		l = self.dfs(node.left) if node.left else node.data
		r = self.dfs(node.right) if node.right else node.data
		if l == r and l == node.data:
			self.res += 1
			return l
		else:
			return -1


class Solution:
	a = 0

	def singlevalued(self, root):

		def tree(root):
			if not root:
				return True
			l = tree(root.left)
			r = tree(root.right)
			if l == False or r == False:
				return False
			if root.left != None and root.data != root.left.data:
				return False
			if root.right != None and root.data != root.right.data:
				return False
			self.a += 1
			return True
		tree(root)
		return self.a


class Solution:

	def singlevalued(self, root):
		res = 0

		def recur(root):
			nonlocal res
			if not root:
				return set()
			cur = recur(root.left)
			cur.update(recur(root.right))
			cur.add(root.data)
			if len(cur) < 2:
				res += 1
			return cur
		recur(root)
		return res


class Solution:

	def singlevalued(self, root):
		dp = {'count': 0}

		def dfs(node):
			if not node:
				return True
			if node:
				if not node.left and (not node.right):
					dp['count'] += 1
					return True
				l = dfs(node.left)
				r = dfs(node.right)
				if l and r:
					if node.left and node.right:
						left = node.left.data
						right = node.right.data
						if left == right and right == node.data:
							dp['count'] += 1
							return True
						else:
							return False
					if node.right:
						if node.right.data == node.data:
							dp['count'] += 1
							return True
						else:
							return False
					if node.left:
						if node.left.data == node.data:
							dp['count'] += 1
							return True
						else:
							return False
				return False
		dfs(root)
		return dp['count']


from sys import setrecursionlimit
setrecursionlimit(100000)

class Solution:

	def singlevalued(self, root):
		ans = [0]

		def recur(node):
			if node is None:
				return True
			left = recur(node.left)
			right = recur(node.right)
			if left and right and (node.left is None or node.left.data == node.data) and (node.right is None or node.right.data == node.data):
				ans[0] += 1
				return True
			return False
		recur(root)
		return ans[0]


class Solution:

	def singlevalued(self, root):
		count = 0

		def helper(root, count):
			if root is None:
				return (True, count)
			(left, count) = helper(root.left, count)
			(right, count) = helper(root.right, count)
			if left == False or right == False:
				return (False, count)
			if root.left and root.data != root.left.data:
				return (False, count)
			if root.right and root.data != root.right.data:
				return (False, count)
			count += 1
			return (True, count)
		(x, y) = helper(root, count)
		return y


class Solution:

	def singlevalued(self, root):
		count = 0

		def solve(root):
			nonlocal count
			if root == None:
				return True
			l = solve(root.left)
			r = solve(root.right)
			if l and r:
				if (root.left == None or root.left.data == root.data) and (root.right == None or root.right.data == root.data):
					count += 1
					return True
			return False
		solve(root)
		return count


class Solution:

	def singlevalued(self, root):

		def postorder(root):
			if root is None:
				return True
			left = postorder(root.left)
			right = postorder(root.right)
			if left and right:
				if root.left is not None and root.left.data != root.data:
					return False
				if root.right is not None and root.right.data != root.data:
					return False
				self.count += 1
				return True
			return False
		self.count = 0
		postorder(root)
		return self.count


class Solution:

	def singlevalued(self, root):

		def dfs(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				self.count += 1
				return root.data
			left = dfs(root.left)
			right = dfs(root.right)
			if (root.data == left or root.left == None) and (root.data == right or root.right == None):
				self.count += 1
				return root.data
			return -1
		self.count = 0
		dfs(root)
		return self.count
		count = 0
		countSingleValued(root, count)
		return count


class Solution:

	def singlevalued(self, root):

		def soln(node):
			if not node:
				return ('#', True)
			(l, fl) = soln(node.left)
			(r, fr) = soln(node.right)
			if not (fl and fr):
				return (l, False)
			if l == '#':
				l = node.data
			if r == '#':
				r = node.data
			if l == r == node.data:
				soln.res += 1
				return (node.data, True)
			return (l, False)
		soln.res = 0
		soln(root)
		return soln.res


class Solution:

	def singlevalued(self, root):
		self.ans = 0

		def dfs(root):
			if root == None:
				return True
			left = dfs(root.left)
			right = dfs(root.right)
			if left and right:
				if root.left and root.left.data != root.data or (root.right and root.right.data != root.data):
					return False
				else:
					self.ans += 1
					return True
			return False
		dfs(root)
		return self.ans