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.
URL: https://leetcode.com/problems/count-univalue-subtrees/
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def __init__(self):
self.__count = 0
def countUnivalSubtrees(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.count_univalue_subtrees(root)
return self.__count
def count_univalue_subtrees(self, root):
if root == None:
return True
if root.left == None and root.right == None:
self.__count += 1
return True
left = self.count_univalue_subtrees(root.left)
right = self.count_univalue_subtrees(root.right)
if (left and right) and (root.left == None or root.left.val == root.val) and (root.right == None or root.right.val == root.val):
self.__count += 1
return True
else:
return False