1110:最近共同祖先
时间: 2024-01-11 18:03:53 浏览: 114
根据提供的引用内容,可以使用递归函数来求解x和y的最近共同祖先。递归函数的定义如下:
```python
def common(x, y):
if x == y:
return x
elif x > y:
return common(x // 2, y)
else:
return common(x, y // 2)
```
根据题目的要求,输入的x和y分别为10和4,那么调用该函数可以得到最近共同祖先为2。
```python
x = 10
y = 4
result = common(x, y)
print(result) # 输出:2
```
相关问题
1110: 最近共同祖先(函数专题)
111题是一道关于二叉树的题目,要求找到两个节点的最近共同祖先。这道题可以用递归的方法来解决,先判断当前节点是否为p或q,如果是则返回该节点,否则递归遍历左右子树,如果左右子树都不为空,则说明p和q分别在当前节点的左右子树中,该节点即为最近共同祖先。如果只有一边不为空,则说明p和q在同一侧,继续递归遍历该侧子树即可。
c语言二叉树共同祖先
以下是两种C语言实现二叉树共同祖先的方法:
方法一:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 查找p或q结点是否在以root为根的二叉树中
bool findNode(BiTree root, BiTNode *p) {
if (root == NULL) {
return false;
}
if (root == p) {
return true;
}
if (findNode(root->lchild, p) || findNode(root->rchild, p)) {
return true;
}
return false;
}
// 查找p和q的最近公共祖先
BiTNode *nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q) {
if (root == NULL || p == NULL || q == NULL) {
return NULL;
}
if (!findNode(root, p) || !findNode(root, q)) {
return NULL;
}
if (root == p || root == q) {
return root;
}
BiTNode *left = nearest_ancestor(root->lchild, p, q);
BiTNode *right = nearest_ancestor(root->rchild, p, q);
if (left != NULL && right != NULL) {
return root;
} else if (left != NULL) {
return left;
} else {
return right;
}
}
```
方法二:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
typedef struct {
BiTNode *elem[100];
int top;
} Stack;
// 初始化栈
void init_stack(Stack *s) {
s->top = -1;
}
// 入栈
void push(Stack *s, BiTNode *node) {
s->top++;
s->elem[s->top] = node;
}
// 出栈
void pop(Stack *s) {
s->top--;
}
// 获取栈顶元素
BiTNode *get_top(Stack *s) {
return s->elem[s->top];
}
// 查找从根结点到指定结点的路径
bool path(BiTree root, BiTNode *node, Stack *s) {
if (root == NULL) {
return false;
}
push(s, root);
if (root == node) {
return true;
}
if (path(root->lchild, node, s) || path(root->rchild, node, s)) {
return true;
}
pop(s);
return false;
}
// 查找p和q的最近公共祖先
BiTNode *nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q) {
Stack s1, s2;
BiTNode *Node1;
init_stack(&s1);
init_stack(&s2);
path(root, p, &s1);
path(root, q, &s2);
Node1 = get_top(&s1);
if (get_top(&s1) != get_top(&s2)) {
return NULL;
}
for (int i = 1; i < s1.top && i < s2.top; i++) {
if (s1.elem[i] != s2.elem[i]) {
return Node1;
}
Node1 = s1.elem[i];
}
return Node1;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)