二叉树中两个节点之间的距离
哪些公司问过
答案要点
- 两节点路径必经 LCA,距离 = dist(LCA, p) + dist(LCA, q)
- 后序递归求 LCA:左右子树都找到则当前即 LCA,否则返回非空一侧
- 从 LCA 出发 DFS 求两个节点的深度
- 也可用父指针加深度,深的先上移再同步上移至相遇
- 时间 O(n)、空间 O(h),处理 p=q、祖先关系、节点不存在等边界
易错点
- 用根到两点深度直接相加,忘记减去 2 倍 LCA 深度
- p 是 q 的祖先时 LCA 处理错误
- 节点不在树中时仍返回错误的距离
面试官常见追问
- 如果有大量查询怎么优化?
- 节点可能不在树中时,经典 LCA 递归有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场