Binary Tree Tilt

Problem Id: 563 Difficulty: Easy Tag: Tree


Intuition

The result could be solved recursivly by using DFS. In the return value of DFS, we could add 2 additional values, one is the sum of all tilts, and another is the sum of all values.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        return self._dfs(root)[1]

    def _dfs(self, node):
        if node is None:
            return 0, 0
        l = self._dfs(node.left)
        r = self._dfs(node.right)
        tilt = l[1] + r[1] + abs(l[0] - r[0])
        return node.val + l[0] + r[0], tilt