Python double recursive but faster?


  • 0
    Y

    I believe this is O(n**2) because for every node we test if the subtree rooted at that node is univalued, which explores all nodes in the subtree. However it runs in 44ms vs 60ms for the bottom-up O(n) approach.

    class Solution(object):
        def countUnivalSubtrees(self, root):
            self.univariates = 0
            self.preorder(root)
            return self.univariates
    
        def preorder(self, root):
            if not root:
                return
            if self.is_univariate(root):
                self.univariates += 1
            self.preorder(root.left)
            self.preorder(root.right)
    
        def is_univariate(self, root):
            if not root:
                return True
            if root.left and root.left.val != root.val:
                return False
            if root.right and root.right.val != root.val:
                return False
            return self.is_univariate(root.left) and self.is_univariate(root.right)
    

Log in to reply
 

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