Lstmxx的空间

1123. 最深叶节点的最近公共祖先

给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。

回想一下：

• 叶节点 是二叉树中没有子节点的节点
• 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
• 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

链接

/**
 * 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)
 *     }
 * }
 */

type Smallest = {
  node: TreeNode | null;
  depth: number
}


function lcaDeepestLeaves(root: TreeNode | null): TreeNode | null {
  function dfs(node: TreeNode | null): Smallest {
    if (node === null) return { node: null, depth: 0 }
    const l = dfs(node.left)
    const r = dfs(node.right)
    if (l.depth > r.depth) return { node: l.node, depth: l.depth + 1 }
    if (l.depth < r.depth) return { node: r.node, depth: r.depth + 1 }
    return { node: node, depth: l.depth + 1 }
  }
  return dfs(root).node
};