How to Tilt a Binary Tree in Java
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};
}
}