N 叉树的最大深度 图解题解

这道题到底在问什么

输入

root = [50,[30,[10,20],80,[60]]]

输出

3

最优解：一步一步想明白

1. 3记牢「先算孩子、取最大、加一层」，下面每一帧都在套它。
2. 4目标:算出根 50 的子树深度先看整棵树。我们要算根 50 的子树深度。办法是从根往下递归:先把每个孩子的子树深度都算清楚，再取最大、加上自己这一层。下面跟着紫色的「当前节点」一路下探。
3. 550 有 2 个孩子走到节点 50（紫色）。它的孩子列表有 2 个:30、80。想知道 50 的深度，得先把这几个孩子的子树深度逐个算出来。
4. 6先深入孩子 30按后序的规矩，先把第一个孩子 30 的子树彻底算完，再回头看 50 剩下的孩子。我们顺着这条边往下走。
5. 730 有 2 个孩子走到节点 30（紫色）。它的孩子列表有 2 个:10、20。想知道 30 的深度，得先把这几个孩子的子树深度逐个算出来。
6. 8先深入孩子 10按后序的规矩，先把第一个孩子 10 的子树彻底算完，再回头看 30 剩下的孩子。我们顺着这条边往下走。
7. 910 没有孩子走到节点 10（紫色）。它的孩子列表是空的，是个叶子，不用再往下了。
8. 1010 子树深度 1叶子 10 没有孩子，最深孩子算 0，加上自己这一层，子树深度就是 1。节点 10 标绿，表示它的深度已经定下来了。
9. 11还剩 1 个孩子孩子 10 那一支已经算完(深度 1)，回到 30。它还有孩子没算，接着深入下一个 20。
10. 1220 没有孩子走到节点 20（紫色）。它的孩子列表是空的，是个叶子，不用再往下了。
11. 1320 子树深度 1叶子 20 没有孩子，最深孩子算 0，加上自己这一层，子树深度就是 1。节点 20 标绿，表示它的深度已经定下来了。
12. 14孩子深度 1、1，最大 130 的孩子都算完了，子树深度分别是 1、1。我们要的是最深的那个，取最大值得到 1。正在判定 30，先别急着定色。
13. 1530 子树深度 2最深的孩子子树是 1，加上 30 自己这一层，30 的子树深度 = 1 + 1 = 2。节点 30 标绿，深度敲定。
14. 16还剩 1 个孩子孩子 30 那一支已经算完(深度 2)，回到 50。它还有孩子没算，接着深入下一个 80。
15. 1780 有 1 个孩子走到节点 80（紫色）。它的孩子列表有 1 个:60。想知道 80 的深度，得先把这几个孩子的子树深度逐个算出来。
16. 18先深入孩子 60按后序的规矩，先把第一个孩子 60 的子树彻底算完，再回头看 80 剩下的孩子。我们顺着这条边往下走。
17. 1960 没有孩子走到节点 60（紫色）。它的孩子列表是空的，是个叶子，不用再往下了。
18. 2060 子树深度 1叶子 60 没有孩子，最深孩子算 0，加上自己这一层，子树深度就是 1。节点 60 标绿，表示它的深度已经定下来了。
19. 21孩子深度 1，最大 180 的孩子都算完了，子树深度分别是 1。我们要的是最深的那个，取最大值得到 1。正在判定 80，先别急着定色。
20. 2280 子树深度 2最深的孩子子树是 1，加上 80 自己这一层，80 的子树深度 = 1 + 1 = 2。节点 80 标绿，深度敲定。
21. 23孩子深度 2、2，最大 250 的孩子都算完了，子树深度分别是 2、2。我们要的是最深的那个，取最大值得到 2。正在判定 50，先别急着定色。
22. 2450 子树深度 3最深的孩子子树是 2，加上 50 自己这一层，50 的子树深度 = 1 + 2 = 3。节点 50 标绿，深度敲定。
23. 25最大深度 = 3所有节点都结算完了。根 50 的两个孩子 30 和 80 子树深度都是 2，取最大 2 再加 1，根的子树深度就是 3。这正是从根到最远叶子那条路上的节点数，答案 = 3。

⚠️ 容易写错的地方

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

from typing import List
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        return 1 + max([self.maxDepth(c) for c in root.children] or [0])

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _children) { val = _val; children = _children; }
};
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        int best = 0;
        for (Node* child : root->children) best = max(best, maxDepth(child));
        return best + 1;
    }

};

import java.util.*;
class Node {
    public int val;
    public List<Node> children;
    public Node() { children = new ArrayList<>(); }
    public Node(int _val) { val = _val; children = new ArrayList<>(); }
    public Node(int _val, List<Node> _children) { val = _val; children = _children; }
}
class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int best = 0;
        for (Node child : root.children) best = Math.max(best, maxDepth(child));
        return best + 1;
    }

}

复杂度

面试官可能追问