Python straightforward solution


  • 6

    Think about a recursive function. Beside the tilt of subtrees, we also need to get the sum of subtrees.
    So I came up with the idea of sub function tilt(root), which returns the tuple (sum, tilt) of tree

    def findTilt(self, root):
            def tilt(root):
                # return (sum, tilt) of tree
                if not root: return (0, 0)
                left = tilt(root.left)
                right = tilt(root.right)
                return (left[0] + right[0] + root.val, abs(left[0] - right[0]) + left[1] + right[1])
            return tilt(root)[1]

  • 1
    K

    Thank you. Same idea but minus unpacking.

    class Solution(object):
        def findTilt(self, root):
            
            def dfs(root):  # get sum of all vals
                if not root:
                    return 0
                
                left = dfs(root.left)
                right= dfs(root.right)
                self.tilt += abs(left - right)
                
                return root.val + left + right
            
            self.tilt = 0
            dfs(root)
            return self.tilt
    

Log in to reply
 

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