题目

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

返回包含原始树中所有 最深节点 的 最小子树 。

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

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

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4] 输出：[2,7,4] 解释： 我们返回值为 2 的节点，在图中用黄色标记。在图中用蓝色标记的是树的最深的节点。注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1] 输出：[1] 解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2] 输出：[2] 解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

提示：

树中节点的数量在 [1, 500] 范围内。
0 <= Node.val <= 500
每个节点的值都是 独一无二 的。

解题思路

这道题可以转化为：找到所有“最深节点”的“最近公共祖先”。

我们需要遍历整棵树，对于每一个节点，我们需要知道两个信息：

它所在的子树的最大深度是多少？ (用来判断哪边更深)
它所在的子树中，包含所有最深节点的那个“最小子树根节点”是谁？ (用来作为返回结果)

递归逻辑 (分治法)

我们可以定义一个递归函数（DFS），对于当前节点 root，它的返回值应该包含两部分：

height: 以当前节点为根的子树的最大深度（或者说高度）。
node: 该子树中满足条件的“最小子树根节点”。

判断规则：

递归左右子树：先拿到左子树的结果 (leftHeight, leftNode) 和右子树的结果 (rightHeight, rightNode)。
比较深度：
- 情况 1：左边更深 (leftHeight > rightHeight)
  - 说明最深的节点都在左边。
  - 当前节点对此无能为力，只能把左边的结果往上传。
  - 返回 (leftHeight + 1, leftNode)。
- 情况 2：右边更深 (rightHeight > leftHeight)
  - 说明最深的节点都在右边。
  - 同理，把右边的结果往上传。
  - 返回 (rightHeight + 1, rightNode)。
- 情况 3：两边一样深 (leftHeight == rightHeight)
  - 这是关键点！ 说明左边有最深节点，右边也有最深节点。
  - 那么当前节点 root 就是连接左右两边最深节点的最近公共祖先（也就是我们要找的最小子树的根）。
  - 返回 (leftHeight + 1, root)。

具体代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 * Val int
 * Left *TreeNode
 * Right *TreeNode
 * }
 */

// 定义一个结构体来同时返回深度和目标节点
type Result struct {
    Node  *TreeNode
    Depth int
}

func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
    return dfs(root).Node
}

func dfs(node *TreeNode) Result {
    // 1. 递归终止条件
    if node == nil {
        return Result{Node: nil, Depth: 0}
    }

    // 2. 后序遍历：先拿到左右子树的结果
    left := dfs(node.Left)
    right := dfs(node.Right)

    // 3. 核心逻辑判断
    // 如果左边更深，说明目标子树在左边
    if left.Depth > right.Depth {
        return Result{
            Node:  left.Node,
            Depth: left.Depth + 1,
        }
    }

    // 如果右边更深，说明目标子树在右边
    if right.Depth > left.Depth {
        return Result{
            Node:  right.Node,
            Depth: right.Depth + 1,
        }
    }

    // 如果两边深度一样，说明当前节点就是这些最深节点的最近公共祖先
    return Result{
        Node:  node,
        Depth: left.Depth + 1,
    }
}

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

beautifulremi

题目

解题思路

递归逻辑 (分治法)

具体代码