当前位置:首页c语言 > 正文

C语言大厂面试经典题目:寻找二叉树中两个节点的最近公共祖先节点

作者:野牛程序员:2023-12-04 15:46:17c语言阅读 3560

编写函数寻找最近公共祖先: 创建一个函数 lowestCommonAncestor,用于在二叉树中寻找两个节点的最近公共祖先。这个函数通过递归的方式实现。基本思路是:

  • 如果当前节点为空,或者找到了其中一个目标节点,就返回当前节点。

  • 在左子树中递归查找最近公共祖先。

  • 在右子树中递归查找最近公共祖先。

  • 如果在左右子树中都找到了目标节点,则当前节点为最近公共祖先。


以下是使用 C 语言实现的二叉树节点结构和寻找最近公共祖先的代码示例:

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

// 定义二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 在二叉树中寻找两个节点的最近公共祖先
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    // 如果树为空,或者找到了 p 或 q,则返回当前节点
    if (!root || root == p || root == q) {
        return root;
    }

    // 在左子树中递归查找最近公共祖先
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);

    // 在右子树中递归查找最近公共祖先
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // 如果在左右子树中都找到了 p 和 q,则当前节点为最近公共祖先
    if (left && right) {
        return root;
    }

    // 如果只在左子树中找到了 p 或 q,则返回左子树的结果
    // 反之,如果只在右子树中找到了 p 或 q,则返回右子树的结果
    return left ? left : right;
}

// 创建新的二叉树节点
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // 构建一棵二叉树
    //        3
    //       / \\
    //      5   1
    //     / \\ / \\
    //    6  2 0  8
    //      / \\
    //     7   4
    struct TreeNode* root = createNode(3);
    root->left = createNode(5);
    root->right = createNode(1);
    root->left->left = createNode(6);
    root->left->right = createNode(2);
    root->right->left = createNode(0);
    root->right->right = createNode(8);
    root->left->right->left = createNode(7);
    root->left->right->right = createNode(4);

    // 需要找的两个节点
    struct TreeNode* p = root->left;
    struct TreeNode* q = root->right;

    // 找到最近公共祖先
    struct TreeNode* result = lowestCommonAncestor(root, p, q);

    // 输出最近公共祖先的值
    printf("Lowest Common Ancestor: %d\\n", result->val);

    // 释放内存
    free(root->left->right->right);
    free(root->left->right->left);
    free(root->left->right);
    free(root->left->left);
    free(root->left);
    free(root->right->right);
    free(root->right->left);
    free(root->right);
    free(root);

    return 0;
}

这个示例创建了一个简单的二叉树,然后调用 lowestCommonAncestor 函数找到节点 p 和节点 q 的最近公共祖先,并输出其值。在程序的结尾部分,释放了动态分配的内存。

野牛程序员教少儿编程与信息学奥赛-微信|电话:15892516892
野牛程序员教少儿编程与信息学竞赛-微信|电话:15892516892
相关推荐

最新推荐

热门点击