Algorithm

Appearance

236. 二叉树的最近公共祖先 ​

  • 题号：236
  • 来源：LeetCode
  • 难度：中等
  • 标签：树 哈希表 DFS 递归
  • 语言：TypeScript
  • 解法：2 个
  • 作者：lmliheng
  • 最近更新：2026-09-27

解法一 ​

TypeScript · O(n) 时间 · O(n) 空间 · 更新于 2026-09-27

父节点哈希表加祖先集合求第一个交点

typescript
/**
 * @difficulty medium
 * @tags 树,哈希表,DFS
 * @time O(n)
 * @space O(n)
 * @note 父节点哈希表加祖先集合求第一个交点
 * @236. 二叉树的最近公共祖先
 */
function TreeNode(val: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val;
    this.left = left===undefined ? null : left;
    this.right = right===undefined ? null : right;
}

let root = new TreeNode(3,new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))), new TreeNode(1, new TreeNode(0), new TreeNode(8)))
let p=root.left
let q=root.right

let TreeMap = new Map()
let PathSet = new Set()
if (root === null && p === root && q === root) {
    return root
}
// 字典存储父节点，重点是任一节点值不相同
const dfs = (root: TreeNode | null) => {
    // 叶子
    if (!root!.left && !root!.right) { return }
    if (root!.left) {
        TreeMap.set(root!.left.val, root)
        dfs(root!.left)
    }
    if (root!.right) {
        TreeMap.set(root!.right.val, root)
        dfs(root!.right)
    }


}
dfs(root)

console.log(TreeMap)


while (p !== undefined) {
    PathSet.add(p?.val)
    console.log("PathSet:", PathSet)
    p = TreeMap.get(p?.val)

}
while (q !== undefined) {
    if (PathSet.has(q?.val)) {
        console.log("找到祖先", q)
    }
    q = TreeMap.get(q?.val)
}

源码：ts/leetcode/236. 二叉树的最近公共祖先.ts

解法二 · TypeScript ​

TypeScript · O(n) 时间 · O(n) 空间 · 更新于 2026-09-27

后序递归，左右子树都返回非空时当前即答案

typescript
/**
 * @difficulty medium
 * @tags 树,递归,DFS
 * @time O(n)
 * @space O(n)
 * @note 后序递归，左右子树都返回非空时当前即答案
 * @236. 二叉树的最近公共祖先（解法二）
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */

// ...
var lowestCommonAncestor = function (root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (root === null || root === p || root === q) { return root }
    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)
    if (left === null) return right
    if (right === null) return left
    return root

};

源码：ts/leetcode/236. 二叉树的最近公共祖先（解法二）.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm