Binary Tree Tilt
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 0. The rule is similar if the node does not have a right child.
Example 1
1
/ \
2 3Input
root = [1,2,3]Output
1Tilt of node 2 is 0, tilt of node 3 is 0, and tilt of node 1 is |2 - 3| = 1, so the total tilt is 1.
Example 2
4
/ \
2 9
/ \ \
3 5 7Input
root = [4,2,9,3,5,null,7]Output
15The node tilts are 0, 0, 0, 2, 7, and 6, so their sum is 15.
Constraints
- The number of nodes in the tree is in the range
[0, 10^4]. -1000 <= Node.val <= 1000