https://leetcode.com/problems/binary-tree-tilt

Just traverse tree, using dfs, where we keep two values: sum of all tilts of current subtree and sum of nodes in current subtree. Then:

  1. If we in None node, we return [0, 0]: we do nat have any subtree and tilt.
  2. Let t1, s1 be tilt and sum of nodef for left subtree and t2, s2 for right subtree. Then how we can ealuate final sum of tilts for given node: it is abs(s1-s2) plus tilts for its children. To evaluate sum of all values in subtree we just need to evaluate s1+s2+node.val.

Complexity: time complexity is O(n), space complexity is O(h).

class Solution:
    def findTilt(self, root):
        def dfs(node):
            if not node: return [0,0]
            t1, s1 = dfs(node.left)
            t2, s2 = dfs(node.right)
            return [t1+t2+abs(s1-s2), s1+s2+node.val]
        return dfs(root)[0]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0563