DoorDash VO 面试题解析：带父指针的二叉树最近公共祖先（LCA 树结构高频题）- 一亩三分地 – 代面试 – VO 辅助

You are given a binary tree where every node contains:

• left pointer
• right pointer
• parent pointer
• value

Given two nodes in this tree, return their Lowest Common Ancestor (LCA).

Below is the structure of the tree:

        A
      /   \
     B     C
   /  \   / \
  D   E  F   G
 /
H           I

You will be given two input nodes, and your task is to return the node that is their lowest shared ancestor in the tree.

Example

Input nodes: H, E
Output: B

Explanation:

• H is under D → B → A
• E is under B → A
• Their lowest common ancestor is B.

这道题是 DoorDash VO 很经典的树结构面试题：
给你两个节点，让你找最近公共祖先（LCA），并且每个节点都有 parent 指针。

有 parent 指针之后，难度其实比传统的 LCA 还低，因为你可以：

1. 从某个节点一路往上爬，把所有祖先记录下来
2. 然后再从另一个节点往上爬，遇到的第一个已经出现过的，就是 LCA

或者也可以用更优雅的方式：
像两个链表求交点那样，让两个指针分别往上爬，走完自己链路后换到对方起点，最终会在 LCA 相遇。

面试官重点看你是否能：

• 把树结构分析清楚
• 用 parent pointer 想出高效的方法
• 逻辑清楚地讲出思路
• 正确处理深度不同的节点

在实际 VO 里，这题属于“稳拿分”的题，只要结构说清楚就能给面试官留下非常好的印象。

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Doordash、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。