979. Distribute Coins in Binary Tree

LeetCode medium оригинал: C# #csharp #graph #leetcode #math #medium #recursion #tree #two-pointers

LeetCode Static

Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.

За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.

Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.

Пример:

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.

C# решение

сопоставлено/оригинал

public class Solution {
    private int moves;
    public int DistributeCoins(TreeNode root) {
        moves = 0;
        Dfs(root);
        return moves;
    }
    private int Dfs(TreeNode current) {
        if (current == null) return 0;
        int leftCoins = Dfs(current.left);
        int rightCoins = Dfs(current.right);
        moves += Math.Abs(leftCoins) + Math.Abs(rightCoins);
        return current.val - 1 + leftCoins + rightCoins;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int moves;
    public int DistributeCoins(TreeNode root) {
        moves = 0;
        Dfs(root);
        return moves;
    }
    private int Dfs(TreeNode current) {
        if (current == null) return 0;
        int leftCoins = Dfs(current.left);
        int rightCoins = Dfs(current.right);
        moves += abs(leftCoins) + abs(rightCoins);
        return current.val - 1 + leftCoins + rightCoins;
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    private int moves;
    public int DistributeCoins(TreeNode root) {
        moves = 0;
        Dfs(root);
        return moves;
    }
    private int Dfs(TreeNode current) {
        if (current == null) return 0;
        int leftCoins = Dfs(current.left);
        int rightCoins = Dfs(current.right);
        moves += Math.abs(leftCoins) + Math.abs(rightCoins);
        return current.val - 1 + leftCoins + rightCoins;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0
        self.dfs(root)
        return self.moves

    def dfs(self, current: Optional[TreeNode]) -> int:
        if not current:
            return 0
        leftCoins = self.dfs(current.left)
        rightCoins = self.dfs(current.right)
        self.moves += abs(leftCoins) + abs(rightCoins)
        return current.val - 1 + leftCoins + rightCoins

Go решение

сопоставлено/оригинал

func distributeCoins(root *TreeNode) int {
    moves := 0
    var dfs func(*TreeNode) int
    dfs = func(current *TreeNode) int {
        if current == nil {
            return 0
        }
        leftCoins := dfs(current.Left)
        rightCoins := dfs(current.Right)
        moves += abs(leftCoins) + abs(rightCoins)
        return current.Val - 1 + leftCoins + rightCoins
    }
    dfs(root)
    return moves
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Algorithm

Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.

Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves.

Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.