Python solution with detailed explanation


  • 0
    G

    Solution

    Count Univalue Subtrees https://leetcode.com/problems/count-univalue-subtrees/?tab=Description

    1. Use post-order traversal.
    2. Sketch different cases when you need to increment count of unique trees.
    3. Case 1: When the node is a child.
    4. Case 2: When left and right sub-trees are unique values and left and right subtrees are not null and root.val is equal to root.left.val and root.right.val.
    5. Case 3 & 4: When left and right sub-trees are unique values and either left or right is None and the one which isnt None has value same as root.
    6. Now design a helper function which returns True or False. True means the tree rooted at root is unique valued.
    7. Base Case: None is unique values and returns None.
    class Solution(object):
        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 and root.left.val != root.val:
                    return False
                if root.right and root.right.val != root.val:
                    return False
                self.count = self.count + 1
                return True
            return False
        
        def countUnivalSubtrees(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.count = 0
            if root == None:
                return 0
            self.helper(root)
            return self.count
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.