This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact

Distribute Coins in Binary Tree (Python)

describe

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return the minimum number of moves required to make every node have exactly one coin.

Example 1:

Input: root = [3,0,0]
Output: 2
Explanation: From 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: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.
Copy the code

Example 3:

Input: root = [1,0,2]
Output: 2
Copy the code

Example 4:

Input: root = [1,0,0,null,3]
Output: 4
Copy the code

Note:

The number of nodes in the tree is n.
1 <= n <= 100
0 <= Node.val <= n
The sum of all Node.val is n.
Copy the code

parsing

We now have an operation that moves coins one at a time from the child node to the parent node. We have an operation that moves coins from the child node to the parent node. Or move from parent node to child node, the result is the minimum number of operations that can have at least one gold on each node.

In fact, if you have n nodes and you have n gold coins, you’re going to have one for each node. This is a binary tree balance problem, and the final number of operations is the unbalanced sum of the left and right subtrees. Take Example 3 as an example, the left subtree imbalance is 1, which is equivalent to the lack of a gold coin, you need to take a gold coin from root, and the right subtree imbalance is 1. So the total number of operations is the sum of the absolute values of the unbalanced gold coins in the left and right subtrees.

We use result to count the total number of operations, and the result of each unbalanced return = current gold + absolute value of gold unbalanced in the left subtree + absolute value of gold unbalanced in the right subtree -1

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def distributeCoins(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.result = 0

        def dfs(node):
            if not node: return 0
            L, R = dfs(node.left), dfs(node.right)
            self.result += abs(L) + abs(R)
            return node.val + L + R - 1

        dfs(root)
        return self.result
        
        	      
		
Copy the code

The results

Submissions in Python online submissions for Distribute Coins in Binary Tree. Memory Usage: Submissions in Python online submissions for Distribute Coins in Binary Tree.Copy the code

Original link: leetcode.com/problems/di…

Your support is my biggest motivation