979.在二叉树中分配硬币

链接：979.在二叉树中分配硬币
难度：Medium
标签：树、深度优先搜索、二叉树
简介：给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。返回使每个结点上只有一枚硬币所需的移动次数。

题解 1 - python

• 编辑时间：2023-07-14
• 执行用时：52ms
• 内存消耗：16.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:
            nonlocal res
            if not node:
                return (0, 0)
            l = dfs(node.left)
            r = dfs(node.right)
            nsum = l[0] + r[0] + 1
            csum = l[1] + r[1] + node.val
            res += abs(nsum-csum)
            return (nsum, csum)
        dfs(root)
        return res

题解 2 - rust

• 编辑时间：2023-07-14
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn distribute_coins(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut res = 0;
        fn dfs(res: &mut i32, node: &Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
            match node {
                None => (0, 0),
                Some(node) => {
                    let node_ref = node.as_ref().borrow();
                    let l = dfs(res, &node_ref.left);
                    let r = dfs(res, &node_ref.right);
                    let nsum = l.0 + r.0 + 1;
                    let csum = l.1 + r.1 + node_ref.val;
                    *res += (nsum - csum).abs();
                    (nsum, csum)
                }
            }
        }
        dfs(&mut res, &root);
        return res;
    }
}

题解 3 - cpp

• 编辑时间：2023-07-14
• 执行用时：8ms
• 内存消耗：13.5MB
• 编程语言：cpp
• 解法介绍：dfs。

#define X first
#define Y second
#define pii pair<int, int>
class Solution {
public:
    int distributeCoins(TreeNode* root) {
        int res = 0;
        function<pii(TreeNode*)> dfs = [&](TreeNode *node) {
            if (!node) return make_pair(0, 0);
            auto l = dfs(node->left), r = dfs(node->right);
            int nsum = l.X + r.X + 1, csum = l.Y + r.Y + node->val;
            res += abs(nsum - csum);
            return make_pair(nsum, csum);
        };
        dfs(root);
        return res;
    }
};

题解 4 - typescript

• 编辑时间：2021-07-25
• 执行用时：76ms
• 内存消耗：41.7MB
• 编程语言：typescript
• 解法介绍：分别统计每个子节点进行递归。

function distributeCoins(root: TreeNode | null): number {
  return get()[0];
  function get(node = root): [number, number, number] {
    if (node === null) return [0, 0, 0];
    let ans = 0;
    let nodeCount = 1;
    let coinCount = node.val;
    let [subAns, subNodeCount, subCoinCount] = get(node.left);
    ans += subAns + Math.abs(subNodeCount - subCoinCount);
    nodeCount += subNodeCount;
    coinCount += subCoinCount;
    [subAns, subNodeCount, subCoinCount] = get(node.right);
    ans += subAns + Math.abs(subNodeCount - subCoinCount);
    nodeCount += subNodeCount;
    coinCount += subCoinCount;
    return [ans, nodeCount, coinCount];
  }
}