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

  |   0 评论   |   625 浏览

原文链接 [每日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:

null

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

评论

发表评论