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

这道题到底在问什么

输入

root=[30,50,15,60,20,85,90,null,null,70,45]

输出

以 20 为根的子树 [20,70,45]

最优解：一步一步想明白

1. 3记牢这句口诀：左右等深当前为答案，否则跟更深那一侧。下面每一帧都在套它。
2. 4根=30，目标找最小子树这是一棵 9 个节点的二叉树，根是 30。我们要找包含全部最深节点的最小子树。最底层的 70 和 45 在深度 3（到根 3 条边），是全树最深的两个节点。直觉上，能同时罩住它们的最小子树，根就是它们的最近公共祖先。下面用一次后序 DFS 把这个结论严格算出来。
3. 570 与 45 深度最大先把目标点亮：70 和 45 都在第 4 层（根算第 1 层，到根 3 条边、深度 3），是全树最深的节点。我们要的子树必须同时包含这两个，而且尽量小。带着这个目标开始后序遍历，注意我们全程不直接去测深度，而是靠每个节点比较左右子树的高度来推断。
4. 6展开 30 的子树下行进入节点 30。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 30。先去它的左孩子。
5. 7展开 50 的子树下行进入节点 50。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 50。先去它的左孩子。
6. 8叶子 60沿当前路径下行，来到节点 60。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
7. 960 高度=1结算叶子 60：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，60 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 60。
8. 10展开 20 的子树下行进入节点 20。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 20。先去它的左孩子。
9. 11叶子 70沿当前路径下行，来到节点 70。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
10. 1270 高度=1结算叶子 70：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，70 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 70。
11. 13叶子 45沿当前路径下行，来到节点 45。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
12. 1445 高度=1结算叶子 45：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，45 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 45。
13. 1520 左右各 1回到节点 20 结算。左子树高度 1，右子树高度 1，两边一样深。这说明 20 的左右两侧各藏着同样深的最深节点，唯一能同时罩住它们的最小子树，就是 20 自己。于是 20 升级为候选答案根，返回高度 2。
14. 16右侧更深 高度=3回到节点 50 结算。左子树高度 1，右子树高度 2，右边更深。最深的节点全在更深那一侧，50 自己虽然能罩住所有最深节点，但会把浅的一侧也带进来，所以不是最小答案。把右侧抬上来的候选根 20 原样继续往上抛，高度更新为 3。
15. 17展开 15 的子树下行进入节点 15。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 15。先去它的左孩子。
16. 18叶子 85沿当前路径下行，来到节点 85。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
17. 1985 高度=1结算叶子 85：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，85 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 85。
18. 20叶子 90沿当前路径下行，来到节点 90。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
19. 2190 高度=1结算叶子 90：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，90 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 90。
20. 2215 左右各 1回到节点 15 结算。左子树高度 1，右子树高度 1，两边一样深。这说明 15 的左右两侧各藏着同样深的最深节点，唯一能同时罩住它们的最小子树，就是 15 自己。于是 15 升级为候选答案根，返回高度 2。
21. 23左侧更深 高度=4回到节点 30 结算。左子树高度 3，右子树高度 2，左边更深。最深的节点全在更深那一侧，30 自己虽然能罩住所有最深节点，但会把浅的一侧也带进来，所以不是最小答案。把左侧抬上来的候选根 20 原样继续往上抛，高度更新为 4。
22. 24答案 = 以 20 为根的子树根 30 结算时，左边高度 3、右边高度 2，左边更深，于是把左边一路抬上来的候选根 20 定为最终答案。点亮的子树 20、70、45 恰好同时罩住两个最深节点 70 和 45，而且是满足条件里最小的一棵。答案就是以 20 为根的子树。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

#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;
    }
};

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);
    }
}

复杂度

面试官可能追问