二叉搜索树的最近公共祖先C语言表示
时间: 2024-10-20 16:07:26 浏览: 31
二叉搜索树(Binary Search Tree,BST)的最近公共祖先(Lowest Common Ancestor,LCA)是指在给定两个节点的情况下,在树中找到它们的最深公共祖先节点。在C语言中,可以使用递归的方式来查找最近公共祖先:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 定义辅助函数,用于递归查找LCA
int findLCA(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (root == NULL || root == p || root == q)
return root;
// 如果p在左子树,q在右子树,那么根就是最近公共祖先
if (root->val > p->val && root->val > q->val)
return findLCA(root->left, p, q);
else if (root->val < p->val && root->val < q->val)
return findLCA(root->right, p, q);
// 否则,根就是最近公共祖先
return root;
}
```
在这个示例中,`findLCA`函数接收三个参数:当前遍历到的节点、需要查找的节点`p`和`q`。如果当前节点为空,或者直接等于`p`或`q`,返回该节点;否则,根据BST的特点,分别检查`p`和`q`在哪一侧,继续在那一侧的子树中查找。
阅读全文