Binary Tree Tilt

分治法

class Solution(object):
    result = 0
    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        self.helper(root)
        return self.result

    def helper(self, root):
        if not root.left and not root.right:
            return root.val

        left, right = 0, 0
        if root.left:
            left = self.helper(root.left)
        if root.right:
            right = self.helper(root.right)

        cumSum = left + right + root.val
        self.result += (abs(left - right))
        return cumSum