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++