Lstmxx的空间

865. 具有所有最深节点的最小子树

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。

一个节点的 子树 是该节点加上它的所有后代的集合。

返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。

链接

/**
 * 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 subtreeWithAllDeepest(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
};