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

[每日 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:

null

We should return its max depth, which is 3.


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


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

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    141 引用 • 35 回帖
  • Tree
    33 引用 • 5 回帖
  • Easy
    93 引用 • 10 回帖
回帖   
请输入回帖内容...