LeetCode-Python-1650. 二叉树的最近公共祖先 III

给定一棵二叉树中的两个节点 p 和 q，返回它们的最近公共祖先节点（LCA）。

每个节点都包含其父节点的引用（指针）。Node 的定义如下：

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

根据维基百科中对最近公共祖先节点的定义：“两个节点 p 和 q 在二叉树 T 中的最近公共祖先节点是后代节点中既包括 p 又包括 q 的最深节点（我们允许一个节点为自身的一个后代节点）”。一个节点 x 的后代节点是节点 x 到某一叶节点间的路径中的节点 y。

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和 1 的最近公共祖先是 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和 4 的最近公共祖先是 5，根据定义，一个节点可以是自身的最近公共祖先。

示例 3:

输入: root = [1,2], p = 1, q = 2
输出: 1

提示:

• 树中节点个数的范围是 [2, 105]。
• -109 <= Node.val <= 109
• 所有的 Node.val 都是互不相同的。
• p != q
• p 和 q 存在于树中。

第一种思路：

如果我们先不断向上遍历找到 root, 那么题目就变成了LeetCode-Python-236. 二叉树的最近公共祖先

第二种思路：

如果你把 parent 指针看成 next，那么这道题其实就是返回两个链表的第一个公共节点。

我们可以使用双指针，遍历到尾部之后跳转到另一个链表，第一个相同的节点就是答案。

举例：

p1, p2, c1, c2, (q1, c1)

      q1, c1, c2, (p1, p2, c1)

指针 i 从 p1 出发，走两步到 c1, 再走两步到 q1， 再走一步到c1遇到 j，c1 即是答案

指针 j 从 q1 出发，走一步到 c1, 再走两步到 p1, 再走两步到 c1 遇到 i

这种走法使得每个指针都走了 diff_p + diff_q + common 步, 最后会在第一个公共节点相遇。

时间复杂度：O（N）

空间复杂度：O（1）

class Solution(object):
    def lowestCommonAncestor(self, p, q):
        """
        :type node: Node
        :rtype: Node
        """
        # find root, then normal medium
        # find the convergence point of two linked list
        # both pointers will move diff_p + diff_q + common
        # p1, p2, c1, c2
        #     q1, c1, c2
        # for i, 2 steps from p1 to c1, 2 steps from c1 to q1 and 1 step from q1 to c1
        # for j, 1 step from q1 to c1, 2 steps from c1 to p1, and 2 steps from p1 to c1
        # eventually, they will meet at c1
        i, j = p, q
        while i != j:
            i = i.parent if i.parent else q
            j = j.parent if j.parent else p
        return i