Binary Tree Tilt

Given the root of a binary tree, return the total tilt of the tree. The tilt of a node is the absolute difference between the sum of values in the left subtree and the sum of values in the right subtree. Pattern focus: Global Variable for Cross-Root Paths. Aggregate subtree sums while updating a global tilt total.

Input Format

root = binary tree root

Output Format

total tilt of the tree

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [1,2,3]

Output:

1

Explanation:

The root has left sum 2 and right sum 3, so tilt = 1.

Example 2:

Input:

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

Output:

15

Explanation:

Add the tilt of every node in the tree.

Loading...
Binary Tree Tilt - Binary Tree DSA Problem