C语言求二叉树中两个结点的最低公共祖先结点
时间: 2023-06-12 20:04:24 浏览: 138
可以通过递归实现求二叉树中两个结点的最低公共祖先结点。具体思路如下:
1. 如果当前节点为NULL,返回NULL。
2. 如果当前节点为p或q,则返回当前节点。
3. 在左子树中查找p和q的最低公共祖先,记为left。
4. 在右子树中查找p和q的最低公共祖先,记为right。
5. 如果left和right均不为NULL,则说明p和q分别在左右子树中,当前节点为它们的最低公共祖先。
6. 如果left和right其中一个为NULL,则说明p和q在同一子树中,返回非NULL的那个节点即可。
以下是C语言实现代码:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (root == NULL || root == p || root == q) {
return root;
}
struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
struct TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
}
return left ? left : right;
}
```
在这段代码中,我们使用了一个结构体TreeNode来表示二叉树的节点,其中包含一个整型值val和左右子树的指针。函数lowestCommonAncestor接受三个参数:二叉树的根节点root,需要查找最低公共祖先的两个节点p和q。函数返回值为p和q的最低公共祖先节点。
在函数内部,我们首先判断当前节点是否为NULL、p或q,如果是,则返回当前节点。然后分别在左右子树中查找p和q的最低公共祖先,并将结果保存在left和right中。如果left和right均不为NULL,则说明p和q分别在左右子树中,当前节点为它们的最低公共祖先,直接返回当前节点即可。如果left和right其中一个为NULL,则说明p和q在同一子树中,返回非NULL的那个节点即可。
阅读全文
相关推荐














