二叉链表中寻找两结点的最近共同祖先

在二叉链表中查找两个节点的最近公共祖先（LCA，Least Common Ancestor）通常涉及到遍历树结构，因为二叉链表实际上可以看作是一棵层次分明的树。LCA是指两个节点之间路径上最近的那个公共节点，其特点是它到每个节点的距离都相等。

这里有一个常见的算法思路，称为“路径压缩”和“分治”思想：

1. **路径压缩**：从根节点开始，对访问过的每一个节点，将其左孩子指针连接到当前节点，右孩子保持不变。这一步可以减少后续查询的时间复杂度，使得查找过程中只需关注一条从根到目标节点的路径。

2. **递归查找**：对于给定的两个节点p和q，你可以先分别找到它们在树中的最远公共祖先，然后再在这个公共祖先的路径上查找最近的一个节点。这可以通过比较p和q的祖父节点，如果它们的祖父节点相同，则这个祖父节点就是LCA；否则，LCA就在祖父节点的子节点中（即p或q所在的那一侧）。

以下是伪代码形式的大致步骤：

def findLCA(root, p, q):
    if root is None or root == p or root == q:
        return root

    left_path = findLCA(root.left, p, q)
    right_path = findLCA(root.right, p, q)

    # 如果一边的路径到达了叶子节点，另一边还没到，那么root就是LCA
    if left_path and not right_path:
        return root
    elif right_path and not left_path:
        return root
    else:   # 两边同时到达，说明root不是LCA，需要继续找
        return left_path if left_path != right_path else None