在二叉树中分配硬币（后序遍历）

水深无声 2023-10-06 14:10 8阅读 0赞

## 在二叉树中分配硬币（后序遍历） ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]

#### 思路： ####

利用后序遍历的信息传递作用进行求解

每次转移操作要么是父节点向左右孩子节点转移，要么是左右孩子节点向父节点输送

递归函数的返回值表示节点多出或需要的硬币数，在转移操作之前，节点本身多出或需要的硬币数root\_need为1-root->val（为负表示多出的硬币数），但需考虑左右孩子节点的情况

对左右孩子节点递归调用递归函数得到左右孩子多出或需要的硬币数，若多出，左右孩子将多出硬币给根节点，若需要，根节点将硬币给左右孩子，因此所需移动的次数ans+=abs( left\_need )+abs( right\_need)，根节点在转移操作后多出或需要的硬币数为root\_need+left\_need+right\_need（若左右孩子需要硬币，转移后根节点需要硬币数增加，左右孩子硬币溢出，根节点需要硬币数减少），将其返回

#### 代码： ####

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        int dfs( TreeNode* root,int& ans )
        {
        
            if( root==NULL )
                return 0;
            int root_need=1-root->val;
            int left_need=dfs( root->left,ans );
            int right_need=dfs( root->right,ans );
            ans+=abs( left_need )+abs( right_need );
            return root_need+left_need+right_need;
        }
        int distributeCoins(TreeNode* root) {
        
            int ans=0;
            dfs( root,ans );
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200803150333405.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200803150353205.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200803150403265.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70