zyf200423 2023-12-13 09:18 采纳率: 0%
浏览 16

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

img


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

  • 写回答

2条回答 默认 最新

  • &春风有信 2023-12-13 09:24
    关注

    可以使用深度优先搜索(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;
    }
    
    
    评论

报告相同问题?

问题事件

  • 创建了问题 12月13日

悬赏问题

  • ¥15 报酬10000,做一个简单的换汇网站
  • ¥15 关于#vue.js#的问题:word excel和ppt预览问题语言-javascript)
  • ¥15 Apache显示系统错误3该如何解决?
  • ¥30 uniapp小程序苹果手机加载gif图片不显示动效?
  • ¥20 js怎么实现跨域问题
  • ¥15 C++dll二次开发,C#调用
  • ¥15 请教,如何使用C#加载本地摄像头进行逐帧推流
  • ¥15 Python easyocr无法顺利执行,如何解决?
  • ¥15 为什么会突然npm err!啊
  • ¥15 java服务连接es读取列表数据,服务连接本地es获取数据时的速度很快,但是换成远端的es就会非常慢,这是为什么呢