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

编写函数寻找最近公共祖先： 创建一个函数 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 的最近公共祖先，并输出其值。在程序的结尾部分，释放了动态分配的内存。