二叉树求根结点到叶子结点的最短距离

在二叉链表存储的二叉树中找到距离根节点最近的叶子结点，可以使用广度优先搜索（BFS）策略，因为BFS遍历顺序是从上到下、从左到右，这样可以在遍历过程中保持与当前节点距离最短的叶子节点。 以下是使用C语言描述的算法： ```c #include <stdio.h> #include <stdlib.h> #include <queue> // 定义二叉树节点 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 用于存储节点指针的队列 typedef struct NodeQueue { TreeNode **data; // 存储节点指针 int front, rear; // 队列头和尾指针 int capacity; // 队列容量 } NodeQueue; // 初始化队列 void initQueue(NodeQueue *q, int capacity) { q->front = q->rear = -1; q->capacity = capacity; q->data = (TreeNode **)malloc(capacity * sizeof(TreeNode *)); } // 入队操作 void enqueue(NodeQueue *q, TreeNode *node) { if (q->rear == q->capacity - 1) { printf("Queue is full, cannot enqueue.\n"); return; } q->data[++q->rear] = node; } // 出队操作 TreeNode *dequeue(NodeQueue *q) { if (q->front == -1) { printf("Queue is empty, cannot dequeue.\n"); return NULL; } TreeNode *temp = q->data[q->front++]; if (q->front > q->capacity / 2) { // 翻转数组以便出队时按顺序访问 for (int i = q->front; i < q->rear; i++) { q->data[i] = q->data[q->capacity - 1 - i]; } q->front = q->rear = q->capacity / 2; } return temp; } // 检查是否是叶子节点 int isLeaf(TreeNode *node) { return node->left == NULL && node->right == NULL; } // 主函数 TreeNode* findNearestLeaf(TreeNode* root) { if (root == NULL) return NULL; NodeQueue queue; initQueue(&queue, 10); // 初始化队列，假设最多有10个节点 enqueue(&queue, root); while (!queue.front == -1) { TreeNode *current = dequeue(&queue); if (isLeaf(current)) { return current; } if (current->left != NULL) { enqueue(&queue, current->left); } if (current->right != NULL) { enqueue(&queue, current->right); } } return NULL; // 如果没有找到叶子节点，则返回NULL } ``` 这个算法首先初始化一个队列，并将根节点入队。然后在循环中不断取出队首节点，检查它是否是叶子节点；如果不是，再将其左右子节点加入队列。当队列为空时，说明没有找到叶子节点，返回`NULL`。

为了计算给定二叉树中距离根节点最近的叶子节点，我们可以使用深度优先搜索（DFS）策略遍历整个二叉树。这里我将简述一种可能的算法步骤： 1. 初始化两个变量： - `minDepth`：记录当前找到的最短路径长度，初始化为无穷大。 - `prevLeaf`：保存最近的叶子节点的引用，初始时为NULL。 2. 遍历树的每个节点： a. 如果遇到叶子节点（没有左右子节点），更新`minDepth`和`prevLeaf`。如果当前节点的深度小于`minDepth`，则更新这两个值。 b. 对于非叶子节点，递归地访问左子树和右子树。 3. 返回`prevLeaf`作为结果，它就是距离根节点最近的叶子节点。 对于二叉树 "A(B(D,E(G,H)),C(,F(I)))"，其中括号表示层次关系，我们首先创建一个二叉链存储结构，并应用上述算法。例如，在C语言中，可以使用结构体表示节点和链接，如： ```c typedef struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; } TreeNode; TreeNode* findNearestLeaf(TreeNode* root) { // ... 实现上述算法 ... } ``` 现在假设已经实现了`findNearestLeaf`函数，你可以调用这个函数并传入给定的二叉树的根节点，得到最近的叶子节点。具体的代码实现会涉及对二叉树的节点进行递归遍历和深度计算，这里由于篇幅限制，我就不给出完整的代码了。