The challenge

Given the root of a binary tree, return the sum of every tree node’s tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as ``. The rule is similar if there the node does not have a right child.

Example 1:

Example 2:

Example 3:

Constraints:

  • The number of nodes in the tree is in the range [0, 10<sup>4</sup>].
  • -1000 <= Node.val <= 1000

Definition for a Binary Tree Node

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

The solution in Java code

class Solution {
    public int findTilt(TreeNode root) {
        if (root == null) return 0;
        
        int[] result = walk(root);
        return result[1];
    }
    
    private int[] walk(TreeNode root) {
        if (root == null) return new int[] {0, 0};
        
        int[] left = walk(root.left);
        int[] right = walk(root.right);
        
        int subtreeSum = left[0] + right[0] + root.val;
        int tiltSum = left[1] + right[1] + Math.abs(left[0] - right[0]);
        
        return new int[] {subtreeSum, tiltSum};
    }
}