My verbose Python solution with recursion


  • 0
    # 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 findTilt(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root: return 0
            if not (root.left or root.right): return self._tilt(root)
            else:
                res = self._tilt(root)
                l, r = root.left, root.right
                if l:
                    res = res + self.findTilt(l)
                if r:
                    res = res + self.findTilt(r)
            return res
        
        def _tilt(self, node):
            lsum = self._sum(node.left) if node.left else 0
            rsum = self._sum(node.right) if node.right else 0
            return abs(lsum-rsum)
        
        def _sum(self, node):
            sum = node.val
            if node.left: sum = sum + self._sum(node.left)
            if node.right: sum = sum+ self._sum(node.right)
            return sum
    

    I know my solution is verbose and inefficient, but the idea is straight forward. Use "_sum" to calculate the summation starting from one specific node, use "_tilt" to calculate the tilt of one node.


Log in to reply
 

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