在下面求一棵二叉树所有叶结点的最大和最小枝长的算法中，填写合适的语句（每个空 缺可以填写 1 条语句），使得算法功能完整。 一棵二叉树中所有叶结点的最大枝长和最小枝长分别定义如下： 1 所谓最大枝长就是二叉树层数（根结点为第 0 层）； 2 所谓最小枝长就是离根结点距离最近的叶结点到根结点的路径上的边数； 3 空树的最大最小枝长都定义为 -1； 4 结点数目 n =1（只有树根）的二叉树最大最小枝长都为 0，n=2 的二叉树 最大最小枝长都为 1。 void FarNearLeaf(BinaryTreeNode *root, int &Far, int &Near) { // 按照后序周游方式求树的最大/小枝长 int rightFar, leftFar, rightNear, leftNear; if ( root == NULL ) { Far = -1; Near = -1; return ; // 空树 } if ( (root->leftPtr == NULL) && (root->rightPtr == NULL) ) { Far = 0; ; return; // 独根/叶结点 } FarNearLeaf (root->leftPtr, leftFar, leftNear); // 递归求左子树最大/小枝长 FarNearLeaf (root->rightPtr, rightFar, rightNear); // 递归求右子树最大小枝长 // 下面填空是求最大枝长，子根 root 的最大枝长是左右子树较大的最大枝长+1； if (leftFar > rightFar) Far = leftFar + 1; else if (!root->leftPtr || !root->rightPtr) { // 单支树，最小枝长为非空子树最小枝长+1 if (root->leftPtr) else } else { // 左右子树均存在, 最小枝长为左右子树较小的最小枝长+1 if (leftNear < rightNear) else } }

if (leftFar > rightFar) Far = leftFar + 1; // 左子树最大枝长大于右子树最大枝长
else Far = rightFar + 1; // 右子树最大枝长不小于左子树最大枝长

if (!root->leftPtr && !root->rightPtr) { // 叶节点，最小枝长为0
Near = 0;
} else if (!root->leftPtr || !root->rightPtr) { // 单支树，最小枝长为非空子树最小枝长+1
if (root->leftPtr) Near = leftNear + 1;
else Near = rightNear + 1;
} else { // 左右子树均存在, 最小枝长为左右子树较小的最小枝长+1
if (leftNear < rightNear) Near = leftNear + 1;
else Near = rightNear + 1;
}

相关问题

假设某棵二叉树有N个叶结点。给定这些叶结点的权值，求所有可能的二叉树中带权路径长度（WPL）的最小值

这是一个经典的哈夫曼编码问题。哈夫曼编码是一种将字符编码为二进制的方法，每个字符的编码都是唯一的，且具有最小的编码长度，可以达到最优压缩效果。

对于这个问题，我们可以按照以下步骤解决：

1. 将叶结点的权值按照从小到大的顺序排序。
2. 取出权值最小的两个叶结点，构建一个新的内部结点，其权值为这两个叶结点的权值之和。
3. 将这个新的内部结点插入到叶结点中，重新排序。
4. 重复步骤2和步骤3，直到只剩下一个根结点为止。
5. 最终构建出的二叉树即为哈夫曼树。

最小的WPL即为哈夫曼树的带权路径长度。

c++程序实现假设某棵二叉树有N个叶结点。给定这些叶结点的权值，求所有可能的二叉树中带权路径长度（WPL）的最小值。

这是一道经典的树形DP问题，可以用动态规划来解决。

1. 定义状态

设 $f[i][j]$ 表示处理叶子结点 $i$ 到 $j$ 之间的最小 WPL。

2. 状态转移方程

对于 $f[i][j]$，枚举根节点 $k$，将二叉树分成左右子树，得到状态转移方程：

$$f[i][j] = \min\limits_{i \leq k < j}\{f[i][k] + f[k+1][j] + \sum\limits_{t=i}^{j}w[t]\}$$

其中，$w[t]$ 表示第 $t$ 个叶子结点的权值。

3. 边界条件

当 $i=j$ 时，$f[i][j]=w[i]$。

4. 最终答案

$f[1][N]$ 即为所求的所有可能的二叉树中带权路径长度的最小值。

5. 时间复杂度

总共有 $\frac{N(N+1)}{2}$ 个状态，每个状态需要枚举 $O(N)$ 个根节点，所以时间复杂度为 $O(N^3)$。

下面是 C++ 代码实现：