具有所有最深节点的最小子树 图解题解

同时罩住所有最深节点的最小子树，找它的根

给一棵二叉树，每个节点的深度就是它到根走过的边数，深度最大的那些节点叫最深节点，可能不止一个。要返回同时包住全部最深节点的那棵最小子树的根——子树就是某个节点连同它下面的所有后代。题面例子 root=[30,50,15,60,20,85,90,null,null,70,45]，最深的是 70 和 45，答案是以 20 为根的子树 [20,70,45]。

先测全树深度再找根，来回两趟麻烦在哪

量出全树最深那层不难，一遍遍历就能拿到最大深度。可深度到手之后呢？最深的 70 和 45 分别挂在 20 的左右两边，散在树的不同角落，你还得再扫一遍把它们全找出来，再求它们的最近公共祖先，也就是两个节点最靠下的那个共同祖先。两遍遍历还要记下每个最深节点在哪，节点一多就容易记乱。

一次后序遍历，每个节点只回传两样东西

不必先测深度。换成后序遍历，也就是等左右两支各自算完了才轮到当前节点收口，让每个节点在回溯时只回传两样东西：这棵子树里包住所有最深节点的那个候选根，和这棵子树的高度。高度从叶子往上数，叶子算 1，每往上一层加 1。父节点手里一旦攥着左右两棵子树的高度，谁深谁浅一比就清楚了，答案在回溯途中就能往上递。

回溯到每个节点，比左右高度决定往上抛谁

每到一个节点，先递归拿到左子树的高度 ld、右子树的高度 rd，空节点的高度算 0。接着分三种情况：左边更深就说明最深节点全在左边，把左子树抬上来的候选根原样往上传、高度记成 ld+1；右边更深就传右子树的候选根、高度记成 rd+1；左右一样深这种情况——两侧各藏着同样深的最深节点，唯有当前这个节点能同时罩住它们，于是候选根就是当前节点自己、高度记成 ld+1。一路回溯到根，根拿到的那个候选根就是答案。

顺着题面这棵树，逐节点算一遍高度和候选根

底层叶子 60、70、45 先结算，叶子左右都是空、高度都是 0、正好相等，各自回传高度 1。到节点 20：左孩子 70 高度 1、右孩子 45 高度 1，一样深，按等深规则 20 自己当候选根、回传高度 2。到节点 50：左孩子 60 高度 1、右孩子那支高度 2，右边更深，把右边的候选根 20 原样抬上来、回传高度 3。右半边同理，叶子 85、90 各回传高度 1，节点 15 左右等深、回传候选根 15、高度 2。最后到根 30：左边高度 3、右边高度 2，左边更深，把左边一路抬上来的候选根 20 定成最终答案，以 20 为根的子树 [20,70,45] 恰好同时罩住 70 和 45。

等深必须留自己，别把高度和深度看成一回事

整棵树只走一遍后序遍历，每个节点回溯时做一次高度比较，时间 O(n)；额外空间是递归栈深度，等于树高 h，树退化成一条链时最坏是 O(n)。等深时若手一滑还往某一侧抛，答案就会偏向那半、漏掉另一侧的最深节点，等深时唯一正确的动作是留下当前节点自己。把回传的高度和题面的深度混为一谈同样会算错：深度从根往下量、越深越大，高度从叶子往上数、越往上越大，回传的自始至终是高度。还有个边界，全树只有一个最深节点时，它没有并列同深的另一半，答案就是这个节点自身的子树。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root: Optional[TreeNode]) -> Tuple[Optional[TreeNode], int]:
            if root is None:
                return None, 0
            l, ld = dfs(root.left)
            r, rd = dfs(root.right)
            if ld > rd:
                return l, ld + 1
            if ld < rd:
                return r, rd + 1
            return root, ld + 1

        return dfs(root)[0]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        using pti = pair<TreeNode*, int>;
        function<pti(TreeNode*)> dfs = [&]( TreeNode* root ) -> pti {
            if (!root) {
                return {nullptr, 0};
            }
            auto [l, ld] = dfs(root->left);
            auto [r, rd] = dfs(root->right);
            if (ld > rd) {
                return {l, ld + 1};
            }
            if (ld < rd) {
                return {r, rd + 1};
            }
            return {root, ld + 1};
        };
        return dfs(root).first;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Pair<K, V> { private K key; private V value; Pair(K key, V value){this.key=key;this.value=value;} K getKey(){return key;} V getValue(){return value;} }
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).getKey();
    }

    private Pair<TreeNode, Integer> dfs(TreeNode root) {
        if (root == null) {
            return new Pair<>(null, 0);
        }
        Pair<TreeNode, Integer> l = dfs(root.left);
        Pair<TreeNode, Integer> r = dfs(root.right);
        int ld = l.getValue(), rd = r.getValue();
        if (ld > rd) {
            return new Pair<>(l.getKey(), ld + 1);
        }
        if (ld < rd) {
            return new Pair<>(r.getKey(), rd + 1);
        }
        return new Pair<>(root, ld + 1);
    }
}