分享一道近期的 Google 算法面试真题，题目不长，但里面有一个比较容易漏掉的条件。

英文原题

Given a binary tree where each edge has a weight that may be positive or negative, cut edges so that every leaf is disconnected from the root. Find the set of cuts with the minimum total edge weight, where additional negative-weight edges may also be cut to further reduce the total cost.

中文题意

给定一棵二叉树，每条边都有权重，可能为正也可能为负。需要切掉一些边，使所有叶子节点都和根节点断开，同时让被切边的总权重尽可能小。

题目特别说明：即使某个子树已经和根节点断开，仍然可以继续切其中的负权边来降低总成本。

面试中的关键点

这题整体可以往 Tree DP / DFS 的方向思考。

其中比较关键的一步，是先想清楚负权边应该如何处理。由于切掉负权边会直接降低总 cost，而且不会破坏“叶子与 root 断开”这一要求，因此它和普通的正权 Tree Cut 问题处理方式并不完全一样。

进一步做 DP 时，则需要比较：

是直接切掉当前 edge，还是保留它、转而在下面的 subtree 中完成切割？

另外，leaf 的边界状态也需要特别处理。

真正面试时，难点往往不是写 DFS，而是能不能在几分钟内识别出这些隐藏条件，并定义出正确的 DP state。

csoahelp 实时面试辅助

类似 Google 这类题，interviewer 往往会在原题基础上继续增加 follow-up。只背过题目或者只知道最终代码，现场依然比较容易卡住。

csoahelp 提供实时文本面试辅助和 Mock Interview，可以在面试过程中协助理解题意、梳理思路、处理 follow-up，并根据 interviewer 的追问实时调整解法。

对于正在准备 Google、Meta、TikTok、Amazon 等公司技术面试的同学，也可以提前通过 Mock Interview 熟悉真实面试节奏。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~