191 / 197 test cases passed solution

  • 1

    My Python solution is following:

    class Solution:
    # @param {TreeNode} root
    # @return {integer}
    def countUnivalSubtrees(self, root):
        if not root: return 0
        if (not root.left) and (not root.right): return 1
        if not root.left: return self.countUnivalSubtrees(root.right) + int(root.right.val == root.val) 
        if not root.right: return self.countUnivalSubtrees(root.left) + int(root.left.val == root.val)
        return int(root.val == root.left.val == root.right.val) + self.countUnivalSubtrees(root.left) + self.countUnivalSubtrees(root.right)

    It passed almost all test cases but failed in certain cases. Who can tell what the problem is ?

  • 0

    This method is not correct indeed, like 1->1->2, which means the root is 1, right node is 1, the right node of right node 1 is 2, you code will return 2. Actually there is only 1 UnivalueSubtree, the last node 2. However you count the "1==1" case, so it's wrong.

Log in to reply

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