Approach: Post-order: return subtree sum, accumulate tilt

def findTilt(self, root):
    self.total = 0
    def dfs(node):
        if not node: return 0
        l = dfs(node.left); r = dfs(node.right)
        self.total += abs(l - r)
        return node.val + l + r
    dfs(root)
    return self.total

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

Full Solution — all languages

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findTilt(self, root):
        self.total = 0
        def dfs(node):
            if not node: return 0
            l = dfs(node.left); r = dfs(node.right)
            self.total += abs(l - r)
            return node.val + l + r
        dfs(root)
        return self.total

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) {
        val = v;
    }
}
class Solution {
    public int findTilt(TreeNode root) {
        total = 0;
        dfs(root);
        return total;
    }
    int total;
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int l = dfs(node.left), r = dfs(node.right);
        total += Math.abs(l - r);
        return node.val + l + r;
    }
}

#include <bits/stdc++.h> using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {
    }
};
class Solution {
    public: int findTilt(TreeNode* root) {
        int total = 0;
        function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
            if (!node) return 0;
            int l = dfs(node->left), r = dfs(node->right);
            total += abs(l - r);
            return node->val + l + r;
        };
        dfs(root);
        return total;
    }
};

/**
 * Tree node shape: { val, left, right }
 * @param {TreeNode} root
 * @return {number}
 */ var findTilt = function(root) {
    let total = 0;
    const dfs = (node) => {
        if (!node) return 0;
        const l = dfs(node.left), r = dfs(node.right);
        total += Math.abs(l - r);
        return node.val + l + r;
    };
    dfs(root);
    return total;
};

Binary Tree Tilt

Example 1

Example 2

Constraints