4082. Minimum Operations to Stabilize a Binary Tree 🔒

难度困难

题目描述

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:

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:

Python3JavaC++Go