Python, Simple with Explanation


  • 11

    If we had each node's subtree sum, our answer would look like this psuedocode: for each node: ans += abs(node.left.subtreesum - node.right.subtreesum). Let _sum(node) be the node's subtree sum. We can find it by adding the subtree sum of the left child, plus the subtree sum of the right child, plus the node's value. While we are visiting the node (each node is visited exactly once), we might as well do the ans += abs(left_sum - right_sum) part.

    def findTilt(self, root):
        self.ans = 0
        def _sum(node):
            if not node: return 0
            left, right = _sum(node.left), _sum(node.right)
            self.ans += abs(left - right)
            return node.val + left + right
        _sum(root)
        return self.ans
    

  • 0
    I

    @awice the 2nd to last statement, why using search() here? Shouldn't it be _sum(root)?


  • 0

    @ian34 correct, I fixed it


  • 0
    I

    @awice returning node.val along with the sum difference of left, right subtree values is brilliant, because the same value node.val will be subtracted anyway. How to think of ideas like this?!?!


  • 0
    S

    @ian34 node.val is not being subtracted. sum of all nodes left subtree and right subtree are being subtracted.

    return node.val + left + right
    is needed to simply calculate the left/right subtree's sum.


  • 0
    I

    @sidharth you are right. The trick here is that the condition null node has 0 tilt, which perfectly fits the statement where returning 0 as the value for a null node. So the recursive function just simply return the sum of left, right subtree including itself, while recording the left, right difference.


  • 0
    G

    @awice yes,you explanation is easy to understand,thx :)


  • 0
    L

    @awice Hi, I think I did the same thing as yours, but I put the function _sum outside of the function findTilt, which ended up being very slow..... Can you help me to analyze the reason why it would be much slower than yours?

    class Solution(object):
        def nodeSum(self, root):
            if root == None:
                return 0
            return root.val + self.nodeSum(root.left) + self.nodeSum(root.right)
        
        def findTilt(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root == None:
                return 0
            root_tilt = abs(self.nodeSum(root.left) - self.nodeSum(root.right))
            return root_tilt + self.findTilt(root.left) + self.findTilt(root.right) 
    

  • 0

    @lizzy0127 You calculate intermediate sums multiple times. For example say there are just 4 nodes in a line 1->2->3->4. You calculate the sum of the subtree "3->4" 3 times instead of once. The complexity is no longer linear in the number of nodes.


Log in to reply
 

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