textit

类似树的深度问题，都可以使用递归实现： 确定递归的参数和返回值：参数就是传入树的根节点，返回值就是树的深度； 确定终止条件：如果为空节点的话，就返回0，表示高度为0； 确定单层递归的逻辑：如果是二叉树，那么先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值，最后再+1（加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。 具体到N叉树，代码如下所示： 时间复杂度：O(n)O(n)O(n)，其中nnn为NNN叉树节点的个数。每个节点在递归中只被遍历一次

n 张多米诺骨牌排成一行 将每张多米诺骨牌垂直竖立. 在开始时 同时把一些多米诺骨牌向左或向右推. 每过一秒 倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌. 同样地 倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌. 如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时 由于受力平衡 该骨牌仍然保持不变. 就这个问题而言 我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力. 给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态 其中: 解释: 第一张多米诺骨牌没有给第二张施加额外的力. 当时间为 $0$ 时 部分骨牌会受到一个初始的向左或向右的力而翻倒. 过了 $1$ 秒后 这些翻倒的骨牌会对其周围的骨牌施加一个力. 具体表现为: 向左翻倒的骨牌 如果它有直立的左边紧邻的骨牌 则会对该直立的骨牌施加一个向左的力. 向右翻倒的骨牌 如果它有直立的右边紧邻的骨牌 则会对该直立的骨牌施加一个向右的力. 接下去需要分析这些 $1$ 秒时受力的骨牌的状态. 如果仅受到单侧的力 它们会倒向单侧; 如果受到两个力 则会保持平衡. 再过 $1$ 秒后 这些新翻倒的骨牌又会对其他直立的骨牌施加力 而不会对正在翻倒或已经翻倒的骨牌施加力. 这样的思路类似于广度优先搜索. 我们用一个队列 $q$ 模拟搜索的顺序; 数组 $\textit{time}$ 记录骨牌翻倒或者确定不翻倒的时间 翻倒的骨牌不会对正在翻倒或者已经翻倒的骨牌施加力; 数组 $\textit{force}$ 记录骨牌受到的力 骨牌仅在受到单侧的力时会翻倒. 我们可以枚举所有连续的没有被推动的骨牌，根据这段骨牌的两边骨牌（如果有的话）的推倒方向决定这段骨牌的最终状态： 如果两边的骨牌同向，那么这段连续的竖立骨牌会倒向同一方向。 如果两边的骨牌相对，那么这段骨牌会向中间倒。 如果两边的骨牌相反，那么这段骨牌会保持竖立