1110: 最近共同祖先（函数专题）

111题是一道关于二叉树的题目，要求找到两个节点的最近共同祖先。这道题可以用递归的方法来解决，先判断当前节点是否为p或q，如果是则返回该节点，否则递归遍历左右子树，如果左右子树都不为空，则说明p和q分别在当前节点的左右子树中，该节点即为最近共同祖先。如果只有一边不为空，则说明p和q在同一侧，继续递归遍历该侧子树即可。

相关问题

1110:最近共同祖先

根据提供的引用内容，可以使用递归函数来求解x和y的最近共同祖先。递归函数的定义如下：

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。

x = 10
y = 4
result = common(x, y)
print(result)  # 输出：2

求最近的共同祖先结点，使用栈。

使用栈来求最近的共同祖先结点，一般是采用后进先出的方式。首先，对于两个结点分别遍历它们的祖先链，将遍历到的结点压入栈中。然后比较两个栈顶的结点是否相同，如果相同，则这个结点即为最近的共同祖先结点。如果不同，则弹出栈顶的结点，继续比较。重复上述步骤直到两个栈顶的结点相同或者其中一个栈为空。