【每天学习一点算法 2026/05/18】二叉树的最近公共祖先

每天学习一点算法 2026/05/18

题目：二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

要找两个指定节点的最近公共祖先，就需要先遍历树找到指定节点所在路径，他们路径相遇节点就是我们要找的最近公共祖先，我们可以利用后序遍历，先访问左右子节点再访问根节点，遇到指定节点就往一级回归传递当前层级节点，如果某一条路径没有指定节点就回归传递 null，当回归到某一层时，左右递归接收到的回归值都不为 null 时，此时的根节点就是指定节点的最近公共祖先。

/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */functionlowestCommonAncestor(root:TreeNode|null,p:TreeNode|null,q:TreeNode|null):TreeNode|null{if(root==p||root==q||!root)returnroot// 遇到指定节点返回当前节点，当前路径走到尽头返回 nullconstleft=lowestCommonAncestor(root.left,p,q)// 递归访问左侧子树，获取路径返回值constright=lowestCommonAncestor(root.right,p,q)// 递归访问右侧子树，获取路径返回值letres=null// 用于存储当前层级回归返回值if(left&&right){// 如果左右路径返回值都有值，表示当前 root 就是最近公共祖先res=root}else{// 左右路径返回值有一个为 null，继续回归判断res=left||right}returnres};

题目来源：力扣（LeetCode）