979.-distribute-coins-in-binary-tree.md

979. Distribute Coins in Binary Tree

{% tabs %} {% tab title="Python" %}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        ## 一开始看到这题的图...
        ## 一直都不明白它到底是什么遍历,但是仔细想要分配儿子和爸爸的信息，应该先获取左右子树的数字。
        ## 然后再再分配，树永远都只有三个点，后序

        self.cost = 0
        self.dfs(root)
        return self.cost
        
        
    def dfs(self,root):
        if not root:
            return 0
    
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        self.cost += abs(left) + abs(right)
        res = root.val + left + right
        return res - 1 # 爸爸我还要keep 1 个
            
        
        

{% endtab %} {% endtabs %}