【每日一题】LeetCode 236. 二叉树的最近公共祖先 TypeScript

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1输出3解释节点5和节点1的最近公共祖先是节点3 。示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4输出5解释节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2输出1提示树中节点数目在范围[2, 105]内。-109 Node.val 109所有Node.val互不相同。p ! qp和q均存在于给定的二叉树中。核心思路1.在当前层中如果p或q和当前节点相等则当前节点是最小共同祖先2.在当前层中如果left和right都不为空证明p和q分别都在左右子树则当前节点是最小共同祖先3.如果不同层返回查找到p或者q的所在层的left或者right继续1、2判断/** * 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) * } * } */ function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null { const dfs (node:TreeNode | null):TreeNode | null { if(node null) return null if(node p || node q) return node const left dfs(node.left) const right dfs(node.right) if(left right) return node return left ? left : right } return dfs(root) };共勉