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

results matching ""

    No results matching ""