二叉树最深间隔最远结点，用c语言

Question

给定一棵非空二叉树，数据域值为不等于0的整数。请编写程序找出其最深层间隔最远的两个结点，输出这两个结点差的绝对值。如图1所示的各二叉树最深层间隔最远的结点为5和8。如果最深层只有一个结点，则输出0。

Answer 1

可以使用深度优先搜索（DFS）来遍历二叉树，并记录遍历到的最深的层数。然后，再次遍历二叉树，找到最深层中距离最远的两个节点。

首先，我们定义一个结构体来表示二叉树的节点：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

然后，创建一个函数来构建二叉树：

TreeNode* buildTree() {
    /* 构建二叉树的过程 */
    return NULL;  /* 返回构建的树的根节点 */
}

创建一个函数来计算两个节点之间的距离：

int distance(TreeNode* node1, TreeNode* node2) {
    int distance = 0;
    while (node1 != node2) {
        node1 = node1->left ? node1->left : node1->right;
        node2 = node2->left ? node2->left : node2->right;
        distance++;
    }
    return distance;
}

创建一个函数来找到最深层的节点：

TreeNode* findDeepestNode(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    TreeNode* left = findDeepestNode(root->left);
    TreeNode* right = findDeepestNode(root->right);
    if (left && right) {
        return root;  /* 左右子树都有节点，当前节点就是最深层的节点 */
    } else if (left) {
        return left;  /* 只有左子树有节点，返回左子树最深层的节点 */
    } else if (right) {
        return right;  /* 只有右子树有节点，返回右子树最深层的节点 */
    } else {
        return NULL;  /* 没有找到节点 */
    }
}

最后，我们创建一个函数来找到最深层间隔最远的两个节点：

int findMaxDistance(TreeNode* root) {
    if (root == NULL) {
        return 0;  /* 空树 */
    }
    TreeNode* deepest = findDeepestNode(root);  /* 找到最深层的节点 */
    int maxDistance = 0;  /* 初始化最大距离为0 */
    if (deepest) {  /* 如果找到节点 */
        maxDistance = distance(deepest, root);  /* 计算最深层的节点到根节点的距离 */
    } else {  /* 没有找到节点 */
        maxDistance = INT_MAX;  /* 设置最大距离为一个很大的数 */
    }
    maxDistance = max(maxDistance, findMaxDistance(root->left));  /* 递归计算左子树的最大距离 */
    maxDistance = max(maxDistance, findMaxDistance(root->right));  /* 递归计算右子树的最大距离 */
    return maxDistance;  /* 返回最大距离 */
}

编写主函数来测试：

int main() {
    TreeNode* root = buildTree();  /* 构建二叉树 */
    int maxDistance = findMaxDistance(root);  /* 找到最深层间隔最远的两个节点的最大距离 */
    printf("The maximum distance between the two deepest nodes is: %d\n", maxDistance);  /* 输出结果 */
    return 0;
}