Binary Tree Tilt

Binary TreeDepth-First SearchRecursionTree

Given the root of a binary tree, calculate the tilt of the whole tree. The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null nodes are considered to have a sum of 0. The tilt of the whole tree is defined as the sum of all nodes' tilts.

Example 1

Input

[
  1,
  2,
  3
]

Output

Explanation. The tilt of node 2 is |0-0|=0, and the tilt of node 3 is also 0. The tilt of node 1 is |2-3|=1. Thus, the tilt of the whole tree is 0+0+1=1.

Example 2

Input

[
  4,
  2,
  9,
  3,
  5,
  null,
  7
]

Output

Explanation. Calculating the tilt for each node yields different values, summed up gives 15.

Example 3

Input

[]

Output

Explanation. An empty tree has a tilt of 0.

Example 4

Input

[
  21,
  7,
  14,
  1,
  1,
  2,
  2,
  3,
  3
]

Output

Explanation. The tilt is calculated by considering the tilt of each individual node and summing them up.

Follow-up: Think about possible ways to improve the efficiency of your solution if the input is a balanced tree. How would your approach change?

Constraints:

The number of nodes in the tree is in the range [0, 10,000]. Every node's value is between -1000000 and 1000000.

Views: 3