536. Tree Tilt
A hanging mobile is modelled as a binary tree root, where every node is a pivot carrying an integer weight. The load of a sub-tree is the sum of all node weights inside it, and an empty sub-tree has load 0. The tilt of a node is the absolute difference between the load of its left sub-tree and the load of its right sub-tree. Return the total of the tilts of all nodes in the tree. A leaf has tilt 0 and an empty tree gives 0. The answer is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- root = [6,1,4,2,null,3,8]
- Output:
- 19
- Explanation:
Node 1 has tilt 2, node 4 has tilt 5, the root has tilt |3 - 15| = 12, and the leaves add 0, giving 19.
Example 2
- Input:
- root = [-3,5,-2]
- Output:
- 7
- Explanation:
The root's tilt is |5 - (-2)| = 7 and the two leaves contribute 0.
Example 3
- Input:
- root = [7]
- Output:
- 0
- Explanation:
A single node has equal (empty) sides, so the total tilt is 0.
Constraints
0 ≤ number of nodes ≤ 500
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)