【每天学习一点算法 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 (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */functionlowestCommonAncestor(root:TreeNode|null,p:TreeNode|null,q:TreeNode|null):TreeNode|null{if(rootp||rootq||!root)returnroot// 遇到指定节点返回当前节点当前路径走到尽头返回 nullconstleftlowestCommonAncestor(root.left,p,q)// 递归访问左侧子树获取路径返回值constrightlowestCommonAncestor(root.right,p,q)// 递归访问右侧子树获取路径返回值letresnull// 用于存储当前层级回归返回值if(leftright){// 如果左右路径返回值都有值表示当前 root 就是最近公共祖先resroot}else{// 左右路径返回值有一个为 null继续回归判断resleft||right}returnres};题目来源力扣LeetCode