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