909-2015-T3

1.原题

试编写算法，求给定二叉树上从根节点到叶子节点的一条路径长度等于树的深度减一的路径（即列出从根节点到该叶子节点的节点序列），若这样的路径存在多条，则输出路径终点在“最左”的一条。

2.算法思想

计算出树的高度，然后再进行类前序遍历，输出路径为最深的、最靠左的一条。分为两部分。1.求树的高度；2.求路径

2.1.求树的高度

这个算法在14年某个题已经涉及到了。通过遍历的方式得出每一个结点的左子树高度和右子树高度，而该结点的高度就是左子树高度和右子树高度较大的那一个+1

2.2.求路径

由于是求最靠左的一条、最深的一条路径，那么用类先序遍历的方式进行探索最有优势。根据先序遍历的特点，我们第一次找到的路径即为最左边的。同时引入了一个变量isFound，这样在找到一条路径之后可以更快跳过后续的递归嵌套。

3.关键代码

/*** @struct treeNode* @brief 二叉树节点的结构体*/
struct treeNode {int data; /**< 节点存储的数据 */struct treeNode *lchild; /**< 左子节点指针 */struct treeNode *rchild; /**< 右子节点指针 */
};/*** @brief 计算二叉树的高度。** 通过递归地计算左右子树的高度，返回树的高度。** @param root 二叉树根节点指针。* @return 返回二叉树的高度。*/
int treeHeight(struct treeNode *root) {if (root == NULL) {return 0; // 如果根节点为空，返回0表示树的高度为0} else {int leftHeight = treeHeight(root->lchild); // 递归计算左子树的高度int rightHeight = treeHeight(root->rchild); // 递归计算右子树的高度// 返回左右子树中较大的高度加上当前节点的高度（加1）return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;}
}/*** @brief 在二叉树中查找具有特定深度的路径** 通过递归遍历二叉树，查找根到叶子节点的路径，其深度等于指定高度，并打印该路径。** @param root 二叉树根节点指针。* @param isFound 指向一个布尔值的指针，用于判断是否已找到特定深度的路径。* @param height 期望的路径深度。* @param depth 当前递归深度。* @param path 用于存储路径节点值的数组。*/
void findPath(struct treeNode *root, bool *isFound, int height, int depth, int path[]) {if (root == NULL || (*isFound) == true) {return; // 如果根节点为空或已找到路径，则直接返回}path[depth] = root->data; // 将当前节点值存入路径数组中if (depth == height - 1) {(*isFound) = true; // 标记已找到路径for (int i = 0; i < height; i++) {printf("%d ", path[i]); // 打印路径节点值}printf("\n");return;} else {depth += 1; // 增加深度findPath(root->lchild, isFound, height, depth, path); // 递归遍历左子树findPath(root->rchild, isFound, height, depth, path); // 递归遍历右子树}
}/*** @brief 寻找二叉树中指定深度的路径** 通过计算二叉树的高度，创建对应高度的数组，并在树中查找深度为高度减一的路径。* 找到后打印该路径上的节点值。** @param root 二叉树根节点指针。*/
void findSpecialPath(struct treeNode *root) {int height = treeHeight(root); // 计算二叉树的高度int path[height]; // 创建与高度相同大小的数组，用于存储路径节点值bool isFound = false; // 指示是否找到特定深度的路径findPath(root, &isFound, height, 0, path); // 查找特定深度的路径
}

4.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>/*** @struct treeNode* @brief 二叉树节点的结构体*/
struct treeNode {int data; /**< 节点存储的数据 */struct treeNode *lchild; /**< 左子节点指针 */struct treeNode *rchild; /**< 右子节点指针 */
};/*** @brief 计算二叉树的高度。** 通过递归地计算左右子树的高度，返回树的高度。** @param root 二叉树根节点指针。* @return 返回二叉树的高度。*/
int treeHeight(struct treeNode *root) {if (root == NULL) {return 0; // 如果根节点为空，返回0表示树的高度为0} else {int leftHeight = treeHeight(root->lchild); // 递归计算左子树的高度int rightHeight = treeHeight(root->rchild); // 递归计算右子树的高度// 返回左右子树中较大的高度加上当前节点的高度（加1）return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;}
}/*** @brief 在二叉树中查找具有特定深度的路径** 通过递归遍历二叉树，查找根到叶子节点的路径，其深度等于指定高度，并打印该路径。** @param root 二叉树根节点指针。* @param isFound 指向一个布尔值的指针，用于判断是否已找到特定深度的路径。* @param height 期望的路径深度。* @param depth 当前递归深度。* @param path 用于存储路径节点值的数组。*/
void findPath(struct treeNode *root, bool *isFound, int height, int depth, int path[]) {if (root == NULL || (*isFound) == true) {return; // 如果根节点为空或已找到路径，则直接返回}path[depth] = root->data; // 将当前节点值存入路径数组中if (depth == height - 1) {(*isFound) = true; // 标记已找到路径for (int i = 0; i < height; i++) {printf("%d ", path[i]); // 打印路径节点值}printf("\n");return;} else {depth += 1; // 增加深度findPath(root->lchild, isFound, height, depth, path); // 递归遍历左子树findPath(root->rchild, isFound, height, depth, path); // 递归遍历右子树}
}/*** @brief 寻找二叉树中指定深度的路径** 通过计算二叉树的高度，创建对应高度的数组，并在树中查找深度为高度减一的路径。* 找到后打印该路径上的节点值。** @param root 二叉树根节点指针。*/
void findSpecialPath(struct treeNode *root) {int height = treeHeight(root); // 计算二叉树的高度int path[height]; // 创建与高度相同大小的数组，用于存储路径节点值bool isFound = false; // 指示是否找到特定深度的路径findPath(root, &isFound, height, 0, path); // 查找特定深度的路径
}/*** @brief 创建新的二叉树节点。** @param data 新节点存储的数据。* @return 指向新节点的指针。*/
struct treeNode *createNode(int data) {struct treeNode *newNode = (struct treeNode *) malloc(sizeof(struct treeNode));newNode->data = data;newNode->lchild = NULL;newNode->rchild = NULL;return newNode;
}/*** @brief 以括号表示法打印二叉树。** @param root 二叉树根节点指针。*/
void printBinaryTree(struct treeNode *root) {if (root == NULL) {return;}printf("(%d", root->data);if (root->lchild != NULL || root->rchild != NULL) {printf(" ");if (root->lchild == NULL) {printf("( )");} else {printBinaryTree(root->lchild);}printf(" ");if (root->rchild == NULL) {printf("( )");} else {printBinaryTree(root->rchild);}}printf(")");
}/*** @brief 以树的结构方式打印二叉树。** @param root 二叉树根节点指针。* @param space 节点之间的间距。*/
void printTreeStructure(struct treeNode *root, int space) {if (root == NULL) {return;}int count = 5; // 调整节点之间的间距printTreeStructure(root->rchild, space + count);for (int i = 0; i < space; i++) {printf(" ");}printf("%d\n", root->data);printTreeStructure(root->lchild, space + count);
}int main() {struct treeNode *root = createNode(10);  // 根节点为10root->lchild = createNode(5);root->rchild = createNode(15);root->lchild->lchild = createNode(3);root->rchild->lchild = createNode(12);root->rchild->rchild = createNode(18);root->rchild->lchild->rchild = createNode(13);root->rchild->rchild->rchild = createNode(9);// 以括号表示法打印二叉树printf("Binary Tree Structure (Parenthesis Representation):\n");printBinaryTree(root);// 以树的结构方式打印二叉树printf("\nBinary Tree Structure:\n");printTreeStructure(root, 0);int height = treeHeight(root);printf("Height of the tree: %d\n", height);// 寻找特定路径并打印printf("Special Path with length equal to tree depth - 1: \n");findSpecialPath(root);return 0;
}

5.输出结果