大家好，我是「阑梦清川」
今天我们来看一下 2026 年 408 真题数据结构部分的第四道选择题。这个题目是关于森林转换成二叉树，并求解二叉树的最小高度。
首先，我们需要补充一些前置知识。题目要求我们将 5 棵独立的树合并成一棵二叉树。森林转换二叉树的核心原则是：左孩子右兄弟。
- 「右叉（右兄弟）：」 指向该节点的兄弟，或者是下一棵树的根。
多棵树之间是如何合并的呢？实际上就是：
- 第二棵树的根作为第一棵树根节点的右兄弟，挂在第一棵树的右边。
- 第三棵树的根作为第二棵树根节点的右兄弟，依此类推。
我们可以举一个简单的例子：假设有三棵树。树 1 的根节点是 A，有两个孩子 B 和 C；树 2 的根节点是 D，有一个孩子 E；树 3 的根节点是 F。它们合并转换后的二叉树，完全符合“左孩子右兄弟”的条件。
A ← 树1的根/ \BD ← 树2的根（挂在A的右边） \ / \CEF ← 树3的根（挂在D的右边）
这个题目需要我们求解合并后二叉树的具体高度。关于高度的求解，我们可以先看一个具体的例子：假设有两棵树，树 A 的高度是 3（层级分别为 A1, A2, A3），树 B 的高度是 2（层级分别为 B1, B2）。按照“左孩子右兄弟”合并后：
树 A 的根节点在第一层，A2 在第二层，A3 在第三层。
树 B 的根节点 B1 挂在 A1 的右边，所以 B1 的位置编号是 2。
树 B 自身高度是 2，但由于它从第二层开始，它的总深度变成了 3。
A1 ← 第1层 / \A2 B1 ← 第2层（B1是下一棵树，挂在A1右边） / /A3 B2 ← 第3层
由此我们可以得到一个关键公式：「总深度 = 位置编号 + 树自身高度 - 1」（减 1 是因为根节点在计算位置和自身高度时被重复计算了一次。）
接下来进入解题策略的关键部分：森林里的 5 棵树有高有矮，为了使总深度最小，应该是高的树放前面，还是矮的树放前面？如果一棵自身很高的树被排在后面，由于它的根节点已经在很深的层次了，再加上它自身的高度，整棵二叉树的深度会变得非常大。因此，最优策略是：「高的树一定要放在前面」。
题目给定了每一棵树的节点数，我们根据公式“高度 = ⌈log₂(n+1)⌉”计算出这 5 棵树的高度分别是：2, 2, 3, 3, 3。按照最优策略，我们需要将高度高的树排在前面。
所以这个时候，节点 4、5、6 的高度都为 3，应该放在前面；节点数量为 2 和 3 的树，它们的高度都是 2，应该放在后面。
这样的话，我们计算一下这棵树的总深度：
- 位置编号为 1：树自身的高度是 3，总深度就是 1 + 3 - 1，所以结果就是 3
- 位置编号为 2：树自身的高度是 3，所以就是 2 + 3 - 1，结果就为 4
- 位置编号为 3：树自身的高度也是 3，所以就是 3 + 3 - 1，结果为 5
- 位置编号为 4：树自身的高度是 2，即 4 + 2 - 1，所以结果就是 5
- 位置编号为 5：树自身的高度是 2，所以就是 5 + 2 - 1，结果就等于 6
所以，这个二叉树的高度就等于所有路径之中最大的深度，这道题目的结果就是 6
