Clean Python Solution


  • 0

    Get sum of all subtrees and check if there exists a subtree the sum of which is half of the sum of root tree.

    # 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 checkEqualTree(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if not root or (not root.left and not root.right):
                return False
            self.val = []
            m = self.getSum(root)
            # print self.val
            return m%2==0 and (m//2 in self.val)
            
        def getSum(self, root):
            # return the sum of this subtree and append to a list 
            s = root.val
            if root.left:
                s += self.getSum(root.left)
            if root.right:
                s += self.getSum(root.right)
            self.val.append(s)
            return s
    

  • 0

    Consider a case: [0, 1, -1].


  • 0

    Here's my solution.

    class Solution:
        def helper(self, node):
            if not node:
                return 0
            s = node.val + self.helper(node.left) + self.helper(node.right)
            if node is not self.root:
                self.set.add(s)
            return s
        def checkEqualTree(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            self.set = set()
            self.root = root
            s = self.helper(root)
            if s % 2 == 0 and s // 2 in self.set:
                return True
            return False
    

Log in to reply
 

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