leetcode-559. N叉树的最大深度刷题笔记（c++）

写在前面

• 难度：简单
• 递归迭代 / 层次(广度)遍历

题目详情

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如，给定一个 3叉树 :
         1
 3      2         4
5 6 null null null null

我们应返回其最大深度，3。

说明:
	树的深度不会超过 1000。
	树的节点总不会超过 5000。
           

ac代码

• 方法1：

  递归计算树深度

class Solution
{
public:
    int maxDepth(Node* root)
    {
        if(!root)
            return 0;
        int maxs = 0;
        for(int i=0; i<root->children.size(); i++)
            maxs = max(maxs, maxDepth(root->children[i]));
        return maxs + 1;
    }
};
           

• 方法2：

  bfs(每访问1层, 长度加1)

  • 类似2叉树层次遍历
    • i++ ：先引用后增加
    • ++i ：先增加后引用

class Solution
{
public:
    int maxDepth(Node* root)
    {
        if(!root)
            return 0;
        queue<Node*> q;
        q.push(root);

        // 当前层的节点个数
        int ll = 0, curCnt=q.size();
        Node* pcur=NULL;
        while(!q.empty())
        {
            pcur=q.front();
            q.pop();

            for(int i=0; i<pcur->children.size(); i++)
                q.push(pcur->children[i]);
            // 当前层访问完毕, 更新树最大深度/下1层节点个数
            if(--curCnt==0)
            {
                ll++;
                curCnt=q.size();
            }
        }
        return ll;
    }
};
           

• 参考文章
  • leetcode-559. N叉树的最大深度(两种解法）-c++