979. 在二叉树中分配硬币

绝地灬酷狼 2022-12-23 03:30 108阅读 0赞

# 题目来源 #

[979. 在二叉树中分配硬币][979.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

class Solution {
        
        /**
         * 从后序遍历的第一个叶子节点开始，假设自己有x个金币，剩余x-1个金币都还给父节点，x-1可能为负数、0、正数
         * x-1 < 0说明不够金币，需要从父节点获得，因此子节点有|x-1|个入方向的操作，次数加上|x-1|
         * x-1 == 0说明刚好，无需与父节点有金币的交换，次数加0
         * x-1 > 0 说明有多余的金币，需要交给父节点，因此子节点有x-1个出方向的操作，次数加上|x-1|
         */
        private int ans = 0;// 移动次数
        public int distributeCoins(TreeNode root) {
        
            lrd(root);
            return ans;
        }
        public int lrd(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            if(root.left != null){
        
                root.val += lrd(root.left);
            }
            if(root.right != null){
        
                root.val += lrd(root.right);
            }
            ans += Math.abs(root.val - 1);
            return root.val - 1;
        }
    }

[979.]: https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8797984179aa40da90292a86cead0be8.png