Find LCA in Binary Tree in Java

最低公共祖先 (LCA) 是二叉树中两个节点的祖先，它是树中最深的包含这两个指定节点作为后代的节点。它在分层设置、网络路由和树形计算等多种应用中发挥着重要作用。

示例 1

• LCA (4, 5) → 2 (因为 2 是包含 4 和 5 作为后代的最低节点)
• LCA (4, 6) → 1 (因为 1 是 4 和 6 的最低公共祖先)

示例 2

• LCA (2, 6) → 4 (因为 4 是包含 2 和 6 作为后代的最低节点)
• LCA (6, 11) → 7 (因为 7 是 6 和 11 的最低公共祖先)

示例 3

• LCA 40 和 50 → 20 (因为 20 是同时是 40 和 50 的祖先的最低节点)。
• LCA 50 和 60 → 10 (因为 10 是不同子树中两个节点的最低公共祖先)。

使用数组存储节点从根到节点的路径的方法

我们分别查找并存储从根到两个节点的路径到两个单独的列表中。通过比较这些路径，我们识别出最后一个公共节点，即 最低公共祖先 (LCA)。此方法通过跟踪确切的遍历序列，确保系统地确定 LCA。

算法

步骤 1： 实现递归，将从根到每个目标节点的路径保存在列表中。如果找到目标节点，则停止进一步的递归。

步骤 2： 如果一个节点未达到目标，则将其从路径中删除，并继续在另一个子树中搜索。这保证了只记录正确的路径。

步骤 3： 同时遍历两条存储的路径，找到它们不同的点。在此点之前的节点是公共祖先。

步骤 4： 在发散之前，两条路径中的最后一个公共节点是最低公共祖先 (LCA)。它是两个目标节点共享的最深节点。

步骤 5： 打印 LCA 节点的值作为结果，因为它代表给定节点的最低共享祖先。

让我们在 Java 程序中实现上述算法。

输出

 
LCA of 4 and 5 is: 2   

时间复杂度： O(N) – 遍历树和比较路径都为 O(N)。

空间复杂度： O(N) – 递归栈和路径存储需要 O(N) 空间。

使用单次遍历的方法

与存储路径不同，可以使用 递归 在一次遍历中找到最低公共祖先 (LCA)。此方法通过验证节点是否位于给定节点的路径上来有效地识别 LCA。

算法

步骤 1： 如果根节点为 null 或等于 n1 或 n2，则将其作为可能的 LCA 返回。

步骤 2： 在左子树中对 n1 和 n2 进行递归搜索，并保存结果。

步骤 3： 在右子树中对 n1 和 n2 进行递归搜索，并保存结果。

步骤 4： 如果左右子树的结果均不为 null，则当前节点是 LCA，因为 n1 和 n2 位于不同的子树中。

步骤 5： 如果只有一个子树产生非 null 结果，则将其作为 LCA 返回；否则，如果两个子树都不包含 n1 或 n2，则返回 null。

让我们在 Java 程序中实现上述算法。

输出

 
LCA of 4 and 5 is: 2   

时间复杂度： O(N)，其中 N 是节点数（因为每个节点都被访问一次）。

空间复杂度： O(H)，其中 H 是树的高度（由于递归调用）。

二叉树中的递归 LCA 方法

二叉树中的递归 LCA 方法利用 深度优先搜索 (DFS) 来识别最低公共祖先。它检查节点是否与给定值之一匹配。如果左右子树都包含一个节点，则当前根成为 LCA。否则，返回非 null 子树的结果作为 LCA。顶部表单

底部表单

算法

步骤 1： 如果根节点为 null，则返回 null。如果它与任一给定节点匹配，则立即返回根节点。

步骤 2： 递归地在左子树和右子树中搜索节点。

步骤 3： 如果两个子树的结果均不为 null，则当前根是最低公共祖先 (LCA)。

步骤 4： 如果只有一个子树返回非 null 值，则将该节点作为 LCA 返回。

步骤 5： 在找到 LCA 之前，检查树中是否存在这两个节点。如果其中任何一个丢失，则返回 null，因为 LCA 不存在。

让我们在 Java 程序中实现上述算法。

输出

 
LCA of 4 and 5 is: 2   

时间复杂度： O(N)，因为该算法最多遍历每个节点一次。

辅助空间复杂度： O(H)，其中 H 是树的高度（对于倾斜树为 O(N)，对于平衡树为 O(log N)）。