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

记录改变生活 Stay hungry, stay foolish! 本文由博客端 https://www.tuhaoxin.cn 主动推送
本贴最后更新于 427 天前,其中的信息可能已经时异事殊

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

    179 引用 • 69 回帖
  • Tree
    35 引用 • 6 回帖
  • Easy
    101 引用 • 10 回帖

赞助商 我要投放

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...