AlgoViz Lab交互式算法学习
Algorithms first

二叉树的最近公共祖先 · 交互式算法学习

找到两个节点的最近公共祖先。

#236 · 二叉树

二叉树的最近公共祖先

Lowest Common Ancestor of a Binary Tree

测试用例root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
树 / 图3 个关键状态
步骤 1左子树找到 p=5。left=5
351620874
推荐

后序递归汇合

时间 O(n)空间 O(h)

若左右子树分别找到 p、q，当前节点就是最近公共祖先。

1function lowestCommonAncestor(root, p, q) {2  if (!root || root === p || root === q) return root;3  const l = lowestCommonAncestor(root.left, p, q),4    r = lowestCommonAncestor(root.right, p, q);5  return l && r ? root : l || r;6}
多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode(int x) { val = x; }8 * }9 */10class Solution {11    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {12        if (root == null || root == p || root == q) {13            return root;14        }15        var left = lowestCommonAncestor(root.left, p, q);16        var right = lowestCommonAncestor(root.right, p, q);17        if (left != null && right != null) {18            return root;19        }20        return left == null ? right : left;21    }22}
交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。
动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。
适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。
AlgoViz Lab

二叉树的最近公共祖先 · 解法对比

AlgoViz Lab

找到两个节点的最近公共祖先。

测试用例
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
题目分类
二叉树
解法对比
2
方案 1

记录父节点再向上找

遍历记录 parent；收集 p 的祖先，再从 q 向上找首次交点。

时间
O(n)
空间
O(n)
方案 2

后序递归汇合

若左右子树分别找到 p、q，当前节点就是最近公共祖先。

时间
O(n)
空间
O(h)