首个共同祖先

难度:

标签:

题目描述

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

For example, Given the following tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Input: 3
Explanation: The first common ancestor of node 5 and node 1 is node 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The first common ancestor of node 5 and node 4 is node 5.

Notes:

All node values are pairwise distinct.
p, q are different node and both can be found in the given tree.

代码结果

运行时间: 38 ms, 内存: 20.4 MB

/*
 * 思路：
 * 使用 Java Stream 的概念解决此问题并不直接。
 * 因为树的遍历和查找过程不符合 Stream 的惰性求值和不可变性的特点。
 * 因此，标准递归解决方案更合适。
 * 这里将代码转换为更具有函数式风格的写法。
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return findLCA(root, p, q);
    }
    private TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = findLCA(root.left, p, q);
        TreeNode right = findLCA(root.right, p, q);
        return (left != null && right != null) ? root : (left != null ? left : right);
    }
}

解释

方法:

这个题解使用了递归的深度优先搜索（DFS）策略来寻找二叉树中两个节点的最低公共祖先。递归函数检查当前节点是否为null，如果是，则返回null。如果当前节点是p或q中的一个，则返回当前节点，表示找到了其中一个节点。然后，递归地在左右子树中查找p和q。如果在左子树中找到了p或q，并且在右子树中也找到了，那么当前节点就是p和q的最低公共祖先。如果只在左子树或右子树中找到了p或q，那么返回相应的非null结果。这个方法利用了二叉树的性质，通过递归来简化查找过程。

时间复杂度:

O(n)

空间复杂度:

O(h)

代码细节讲解

🦆

在`lowestCommonAncestor`方法中，如果p和q都不在树中会发生什么？函数将返回什么结果？

▷

在这种情况下，由于递归函数`dfs`会在没有找到p或q的情况下返回`None`，最终的结果将是`None`。这是因为每次递归调用都不会找到p或q，导致所有递归调用都返回`None`，最终`lowestCommonAncestor`函数也将返回`None`。

🦆

题解中提到，如果在左右子树中都找到了p或q，当前节点就是最低公共祖先。但如果p是q的祖先（或反之），递归会如何处理这种情况？

▷

如果p是q的祖先，那么在递归搜索中，当搜索到p时，它的一侧（可能是左或右）将继续搜索并可能找到q，而另一侧将返回`None`。由于p节点已经找到了q，递归将会在p处停止并将p作为结果返回。同样，如果q是p的祖先，也会有类似的处理。因此在这种情况下，p或q本身会被返回作为最低公共祖先。

🦆

该算法是否能处理含有重复值节点的二叉树？如果树中存在多个具有相同值的节点，这种实现还是有效吗？

▷

这种实现假定每个节点的值是唯一的，因为它依赖于节点值来判断是否找到了p或q。如果树中存在具有相同值的多个节点，这可能会导致错误地识别最低公共祖先，因为函数可能会错误地将具有相同值但不是目标p或q的节点当作p或q返回。因此，在节点值可能重复的情况下，这种实现不是有效的。需要修改实现，以便它基于节点的身份（例如内存地址或唯一标识符）而不是值来比较节点。

首个共同祖先

题目描述

代码结果

解释

代码细节讲解

相关问题