How do I approach solving the Distribute Coins in Binary Tree problem?

Use depth-first search (DFS) to traverse the tree and track the number of coins that need to be moved, calculating the minimum moves as you go.

What is the optimal time complexity for solving this problem?

The optimal time complexity is O(n), where n is the number of nodes in the tree, as each node must be visited exactly once.

What are the common pitfalls when solving this problem?

Overcomplicating the traversal or failing to track coin movement correctly between nodes are common pitfalls.

How does DFS help in solving the Distribute Coins in Binary Tree problem?

DFS allows you to efficiently traverse the tree while keeping track of coin surpluses or deficits, ensuring the minimum number of moves.

What is the space complexity of the solution?

The space complexity is O(n) due to the recursion stack during DFS traversal and the need to store node values.

#979

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

在二叉树中分配硬币

给你一个有 n 个结点的二叉树的根结点 root ，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点移动到父结点。返回使每个…

树深度优先搜索二叉树

题目描述

给你一个有 n 个结点的二叉树的根结点 root ，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。

在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点移动到父结点。

返回使每个结点上只有一枚硬币所需的最少移动次数。

示例 1：

输入：root = [3,0,0]
输出：2
解释：一枚硬币从根结点移动到左子结点，一枚硬币从根结点移动到右子结点。

示例 2：

输入：root = [0,3,0]
输出：3
解释：将两枚硬币从根结点的左子结点移动到根结点（两次移动）。然后，将一枚硬币从根结点移动到右子结点。

提示：

树中节点的数目为 n
1 <= n <= 100
0 <= Node.val <= n
所有 Node.val 的值之和是 n

lightbulb

解题思路

方法一：DFS

我们定义一个函数 $\textit{dfs(\textit{node})}$ ，表示以 $\textit{node}$ 为根节点的子树中，金币的超载量，即金币的数量减去节点数。如果 $\textit{dfs(\textit{node})}$ 为正数，表示该子树中金币的数量多于节点数，需要将多余的金币移出该子树；如果 $\textit{dfs(\textit{node})}$ 为负数，表示该子树中金币的数量少于节点数，需要将不足的金币移入该子树。

在函数 $\textit{dfs(\textit{node})}$ 中，我们首先遍历左右子树，获得左右子树的金币超载量 $\textit{left}$ 和 $\textit{right}$ 。那么当前移动的次数需要加上 $|\textit{left}| + |\textit{right}|$ ，即将左右子树中的金币移动到当前节点。然后，我们返回整个子树的金币超载量，即 $\textit{left} + \textit{right} + \textit{node.val} - 1$ 。

最后返回移动的次数即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(h)$ 。其中 $n$ 和 $h$ 分别是二叉树的节点数和高度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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: Optional[TreeNode]) -> int:
        def dfs(root):
            if root is None:
                return 0
            left, right = dfs(root.left), dfs(root.right)
            nonlocal ans
            ans += abs(left) + abs(right)
            return left + right + root.val - 1

        ans = 0
        dfs(root)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Understanding DFS traversal and how to track state across nodes is crucial.
question_mark
Candidates should be able to explain the greedy approach used to optimize the number of moves.
question_mark
The ability to optimize space complexity while traversing the tree is a key aspect to evaluate.

warning

常见陷阱

外企场景

error
Overcomplicating the tree traversal, leading to unnecessary computations.
error
Forgetting to account for coin transfers between child and parent nodes correctly.
error
Not properly tracking the surplus or deficit of coins at each node during the DFS traversal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than one coin per node, but still minimizing the number of moves to distribute coins evenly.
arrow_right_alt
Considering a non-binary tree structure for a similar distribution problem.
arrow_right_alt
Handling large tree sizes and ensuring the DFS is optimized for performance.

help

常见问题

外企场景

继续练习

#971 翻转二叉树以匹配先序遍历 #987 二叉树的垂序遍历 #988 从叶结点开始的最小字符串