最近公共祖先（LCA）解法：并查集与深度搜索

"这篇博客主要讨论了如何解决最近公共祖先（LCA）问题，即在一个二叉树中找到两个给定节点的最近公共祖先。文章提到了三种不同的情况，并提供了相应的解决方案。情况1是二叉查找树，情况2是具有parent指针的普通二叉树，情况3是仅包含left和right指针的普通二叉树。对于每种情况，作者都给出了详细的思路和代码实现片段。" 在二叉树中，最近公共祖先（LCA）问题是一个经典的问题。本文通过三个具体的情况来阐述解决这个问题的方法。 **情况1：二叉查找树** 对于有序的二叉查找树，求解LCA非常直观。从根节点开始，比较当前节点值与目标节点值，根据大小关系决定向左子树还是右子树遍历。如果当前节点值在两个目标节点之间，那么当前节点就是它们的LCA。这个过程可以递归进行，直到找到目标节点或遍历完所有节点。 **情况2：普通二叉树，节点有parent指针** 在这种情况下，我们可以从两个给定的节点开始，沿着parent指针回溯到根节点，形成两条路径。这两条路径会在某个节点相遇，这个相遇点就是LCA。通过计算两个路径的长度，让较长的路径先走完两者长度之差，然后同时前进，直到两个路径的节点相等。 **情况3：普通二叉树，无parent指针** 当没有parent指针时，我们需要记录从根节点到每个目标节点的路径。这可以通过深度优先搜索（DFS）实现，每次访问一个节点时，将它添加到相应路径的vector中。之后，比较两个路径，找到它们相同部分的起始节点，这个节点就是LCA。例如，如果路径1是3,4,6,10，路径2是6,10，那么6就是LCA。 文章中提供的代码片段展示了如何实现这些算法，例如`bool nodePath(bstNode* pRoot, int value, std::vector<bstNode*>& path)`函数用于在二叉树中寻找给定值的节点，并记录路径。 解决LCA问题需要根据二叉树的结构选择合适的策略。有序的二叉查找树可以直接比较节点值，而无序的二叉树则可能需要记录路径并比较。在实际编程中，理解和掌握这些方法对于处理二叉树相关的问题至关重要。