[每日 LeetCode] 559. Maximum Depth of N-ary Tree

原文链接 [每日 LeetCode] 559. Maximum Depth of N-ary Tree

Description:

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

本题要求 N 叉树的最大深度，可参考[每日 LeetCode] 104. Maximum Depth of Binary Tree 的思想，使用递归和非递归方法。

• 递归方法。主函数中使用递归，首先判空，否则就是遍历子结点数组，然后对每个子结点调用递归函数的返回值加 1 后跟 res 相比，取较大值更新结果 res 即可。

• 非递归方法。借助队列 queue，BFS 的经典，对 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 maxDepth(Node* root) {
        if (!root) return 0;
        int res = 1;
        for (auto child : root->children) {
            res = max(res, maxDepth(child) + 1);
        }
        return res;
    }
};
​

运行时间：148ms

运行内存：32.1M

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 maxDepth(Node* root) {
        if (!root) return 0;
        int res = 0;
        queue<Node*> q{{root}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto t = q.front(); 
                q.pop();
                for (auto child : t->children) {
                    if (child) 
                        q.push(child);
                }
            }
            ++res;
        }
        return res;
    }
};
​

运行时间：140ms

运行内存：32.8M