This is the 28th day of my participation in the First Challenge 2022

The title

979. Allocate coins in a binary tree

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

Train of thought

  • First of all, if we traverse from top to bottom, we cannot determine whether the coins with many current elements should be thrown to the left or the right, so we can only search from bottom to top to achieve the fastest performance.

  • Again, the tree problem becomes a recursive problem, so how do we determine the body of the recursive function, that is, to do something at each node:

    • First, the remaining coins of left and right child nodes should be obtained. This value may be positive or negative, because if there are not enough child nodes, the coins can be obtained from the parent node, and if there are more child nodes, they can be thrown to the parent node for processing.

    • Secondly, after obtaining the remaining number of left and right nodes, we need to subtract one, which is used up by the current node. Then, if this value is used up by one and there is still surplus or insufficient, then we need to move the node. Remember here that no matter whether it is more or less, the number we want to move is the absolute value;

    • After the final processing, the remaining number of the current node is returned to the parent node.

  • Then at the code level we just recursively iterate through our root node and calculate how many coins need to be moved and how many times.

implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var distributeCoins = function(root) {
    // Record the total number of moves
    let result = 0;

    // Determine how many coins need to be moved to the current node, or how many coins need to be moved to the node
    function findChildCount(node) {
        // The node is not null
        if(! node)return 0;

        // The number of left and right nodes minus the coin consumed by itself
        node.val += findChildCount(node.left) + findChildCount(node.right) - 1;
        
        // The rest of it needs to be moved. Take the absolute value
        result += Math.abs(node.val);

        // The parent node can continue to use it
        return node.val;
    }


    findChildCount(root);

    return result;
};

Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.