“This is the 29th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

Given the root of a binary tree with N nodes, there should be node. Val pairs at each node in the tree, and there should be N coins in total.

In one move, we can select two adjacent nodes and move a coin from one node to the other. (Moves can be from parent to child or from child to parent.) .

Returns the number of moves required to have only one coin at each node.

Example 1:

Input: [3,0,0] output: 2 explanation: starting at the root of the tree, we move one coin to its left child and one coin to its right child.Copy the code

Example 2:

Input: [0,3,0] output: 3 explanation: starting with the left child of the root, we move two coins to the root [move twice]. Then, we move a coin from the root to the right child.Copy the code

Example 3:

Input: [1,0,2] output: 2Copy the code

Example 4:

Input: [1,0,0,null,3] output: 4Copy the code

Tip:

  1. 1<= N <= 100
  2. 0 <= node.val <= N

Their thinking

So first of all, we can break down the number of moves we’re looking for into the number of moves we need at each node. And then the question is how do you figure out how many moves you need at each node? Since this requires only one coin per node, if the current node is a leaf node:

  1. If there is no coin at this node, then you need to move a coin over
  2. If the number of coins in this node is greater than 1, it needs to be removednode.val-1coin

The number of coins that move above is the number of coins that need to move at this node. What if the current node is not a leaf? And then you need to know what the left and right subtrees are

  1. If the number of coins in the left and right subtrees is redundant, it will give the current node a certain number of coins if the number of coins plus the number of coins in the current nodenode.valGreater than 1, the current node needs to move any extra coins up
  2. If the left and right subtrees don’t have enough coins, they need to get a certain number of coins from the current node, and if the current node doesn’t have any, they need to get a certain number of coins from its parent

Here we assume that the number returned by the left and right subtrees is L and r. If the value is 0, it means that the subtree does not need to claim coins and has no excess coins. If it is positive, it means that the subtree has excess coins. Based on the above conditions, the current node should return the value l+r+node.val-1 up, and the number of moves required by the current node is the absolute value of L +r+node.val-1, because both taking and giving up require the corresponding number of moves. Based on the above analysis, it is obvious that this problem needs to recursively process each node in the binary tree, and determine the operation times of the current node based on the information returned by the subtree in the process of backtracking, so we need to use the sequential traversal to process the binary tree.

Code implementation

Var distributeCoins = function (root) {var distributeCoins = function (root) {function preorder(node) {// If the current node is empty, If (node === null) return 0 Const l = preorder(node.left), r = preorder(node.right), step = l + r + node.val-1; Res += math.abs (step) return step} preorder(root) return res}Copy the code

At this point we are done with Leetcode-979 – allocating coins in the binary tree

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻