题目描述

给定一棵 n 叉树，返回它最大的深度。

最大的深度指的是从根结点到最远的叶子结点的最长路径经过的结点个数。

例如，给定一棵 3叉树：

返回其最大的深度 3。

注意

• 树的深度最大为 1000。
• 总结点个数最多为 5000。

算法

(深度优先遍历) $O(n)$

1. 按照深度优先遍历的方式，自底向上获取当前结点到叶子结点的最大深度。
2. 叶子结点的深度为 1。递归时，返回当前结点的子结点中深度最大的结点然后加 1。

时间复杂度

• 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int dfs(Node *r) {
        if (r == NULL)
            return 0;

        int d = 1;
        for (auto ch : r -> children)
            d = max(d, dfs(ch) + 1);

        return d;
    }
    int maxDepth(Node* root) {
        return dfs(root);
    }
};