Skip to content

4082. Minimum Operations to Stabilize a Binary Tree πŸ”’

DifficultyHard

Description

You are given the root of a binary tree. Each node contains an integer value representing its current state.

A binary tree is considered stable if for every node u:

  • If u.left exists, then |u.val - u.left.val| <= 1
  • If u.right exists, then |u.val - u.right.val| <= 1

In one operation, you may choose any node and increase or decrease its value by 1.

Return the minimum number of operations required to make the entire binary tree stable.

 

Example 1:

Input: root = [5,8,3]

Output: 3

Explanation:

  • Let u be the root node with value 5. Decrease the left child value from 8 to 6 using 2 operations. Then |u.val - u.left.val| = |5 - 6| = 1.
  • Increase the right child value from 3 to 4 using 1 operation. Then |u.val - u.right.val| = |5 - 4| = 1.
  • Thus, the answer is 2 + 1 = 3.

Example 2:

Input: root = [2,-1,-4]

Output: 5

Explanation:

  • Let u be the root node with value 2. Decrease the value of u from 2 to βˆ’2 using 4 operations.
  • Decrease the right child value from βˆ’4 to βˆ’3 using 1 operation. Then |u.val - u.right.val| = |-2 - (βˆ’3)| = 1.
  • Thus, the answer is 4 + 1 = 5.

Example 3:

Input: root = [0,-2,2,-3,null,1]

Output: 3

Explanation:

​​​​​​​​​​​​​​​​​​​​​

  • Let u be the root node with value 0. Increase the left child value from βˆ’2 to βˆ’1 using 1 operation, and decrease the right child value from 2 to 1 using 1 operation.
  • Now |u.val - u.left.val| = |0 - (βˆ’1)| = 1 and |u.val - u.right.val| = |0 - 1| = 1.
  • Let v be the left child of u, now having value βˆ’1. Increase its left child from βˆ’3 to βˆ’2 using 1 operation so that |v.val - v.left.val| = |βˆ’1 - (βˆ’2)| = 1.
  • The right subtree already satisfies the condition since |1 - 1| = 0.
  • Thus, the answer is 1 + 1 + 1 = 3.​​​​​​​

 

Constraints:

  • The number of nodes in the tree is in the range [1, 5 * 104].
  • -105 <= Node.val <= 105

Solutions

Solution 1

1


1


1


1

Comments