⚡Flashcard Drill➔
NeetCode #420LC-1650MediumTrees
← Back to All Problems

#420 · #1650 · Lowest Common Ancestor of a Binary Tree III(二叉树的最近公共祖先 III)

📌 Problem Statement & Constraints

Given two nodes p and q in a binary tree where each node has a parent pointer, return their lowest common ancestor. Constraints: the number of nodes is in [2, 10^5], all values are distinct.

💡 Core Algorithmic Approaches

  1. With parent pointers, the problem is identical to finding the intersection of two singly linked lists.
  2. Advance both pointers one step at a time; when one reaches the top (its parent is None), redirect it to the other node.
  3. After at most depth(p) + depth(q) steps, both pointers have travelled the same total distance and meet at the LCA.
  4. This needs no depth computation and uses O(1) space.

💻 Benchmark Python3 Implementation

class Solution:
    def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
        a, b = p, q
        while a is not b:
            # when a chain ends, continue along the other chain
            a = a.parent if a.parent else q
            b = b.parent if b.parent else p
        return a

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(depth(p) + depth(q)): both pointers travel the combined path length.
💾 Space Complexity
O(1): two pointers.

⚠️ Interview Pitfalls & Follow-ups

  • Not switching chains at the root: the pointers would simply reach None and never meet.
  • Computing the depths and aligning the pointers: correct and O(1) space, but the chain-switching trick is shorter.
  • Using a set of visited ancestors: O(h) space for the same result.
  • Assuming the nodes are at the same depth: they need not be, which is exactly what the switching equalises.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems

中文速览与面试要点

二叉树的最近公共祖先 III

(这是一个 交互式问题 )给定一棵二叉树中的两个节点 p 和 q,返回它们的最近公共祖先节点。每个节点除了左右儿子节点之外,还包含一个 parent 指针指向它的父节点。约束:树中节点数目在范围 [2, 10^5] 内;-10^9 ≤ Node.val ≤ 10^9;所有 Node.val 互不相同;p != q;p 和 q 均存在于给定的二叉树中。

核心要点

  • 双指针「走对方的路」(标准解) :从 p 出发沿 parent 向上,到根后跳到 q 继续;从 q 出发同理。两个指针走的总路程相同,必然在 LCA 相遇。
  • 与 160(相交链表)完全同构 :把「向上到根」视为链表,LCA 就是两条链的「交点」。
  • 为什么必然相遇 :设 p 到 LCA 的距离为 a、q 到 LCA 的距离为 b、LCA 到根的距离为 c。两个指针各走 a + b + c 步后同时到达 LCA。
  • 复杂度 :O(h) 时间、O(1) 空间。

常见陷阱

  • 用 a.val != b.val 判断相遇 :必须用对象身份 is (虽然本题值互不相同,但语义上应比较对象)。
  • 跳到起点时未判断 parent 为 None :根节点的 parent 为 None,会抛 AttributeError。
  • 记录访问过的祖先集合 :需要 O(h) 空间;双指针法 O(1)。

参考实现

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        a, b = p, q
        while a is not b:
            # 到根后跳到另一个起点
            a = a.parent if a.parent else q
            b = b.parent if b.parent else p
        return a