559. Maximum Depth of N-ary Tree

深藏阁楼爱情的钟 2022-04-22 23:18 27阅读 0赞

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:

![narytreeexample.png][]

We should return its max depth, which is 3.

**Note:**

1.  The depth of the tree is at most `1000`.
2.  The total number of nodes is at most `5000`.

方法一：递归

/*
    // 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 == NULL)
    		return 0;
    
    	int depth = 0;		
    	for (int i = 0; i < root->children.size(); i++)
    	{
    		depth = max(depth, maxDepth(root->children[i]));
    	}	
    	return depth+1;
    }
    };

方法二：迭代

/*
    // 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 == NULL)
    		return 0;
    	int maxNum = 0;
    	queue<Node*>  nodes;
    	nodes.push(root);
    	int count = 1;
    	int nextCount = 0;
    	while (!nodes.empty())
    	{
    		count = nodes.size();
    		for (int i = 0; i < count; i++)
    		{
    			Node* temp = nodes.front();
    			nodes.pop();			
    			int len = temp->children.size();
    			for (int i = 0; i < len; i++)
    			{
    				nodes.push(temp->children[i]);
    			}		
    		}
    		maxNum++;
    	}
    	return maxNum;
    }
    };

[narytreeexample.png]: https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-Maximum Depth of Binary Tree

Problem: > > Given a binary tree, find its maximum depth. > > > The maximum depth i

Bertha 。/ 2022年08月09日 03:14/ 0 赞/ 8 阅读

相关 LeetCode: Maximum Depth of Binary Tree

题目如下： Given a binary tree, find its maximum depth. The maximum depth is the number of

桃扇骨/ 2022年08月06日 09:13/ 0 赞/ 4 阅读

相关 #104 Maximum Depth of Binary Tree

再来选一道通过率最高的题目~ [\104 Maximum Depth of Binary Tree ][104 Maximum Depth of Binary Tree]

朱雀/ 2022年08月02日 04:58/ 0 赞/ 160 阅读

相关 LeetCode 104. Maximum Depth of Binary Tree

废话不多说，先看题目： Given a binary tree, find its maximum depth. 题目意思：就是要求得到二叉树的深度或者高度学过数据结构

红太狼/ 2022年07月27日 13:39/ 0 赞/ 153 阅读

相关 [leetcode]--104. Maximum Depth of Binary Tree

Question 104： > Given a binary tree, find its maximum depth. > > The maximum depth is

缺乏、安全感/ 2022年07月11日 14:29/ 0 赞/ 160 阅读

相关 104. Maximum Depth of Binary Tree

/\ Given a binary tree, find its maximum depth. The maximum depth is the nu

Dear 丶/ 2022年06月10日 14:10/ 0 赞/ 155 阅读

相关 97. Maximum Depth of Binary Tree

97. Maximum Depth of Binary Tree Description Given a binary tree, find its max

痛定思痛。/ 2022年05月27日 04:53/ 0 赞/ 179 阅读

相关 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes a

电玩女神/ 2022年05月04日 09:27/ 0 赞/ 258 阅读

相关 559. Maximum Depth of N-ary Tree

Given a n-ary tree, find its maximum depth. The maximum depth is the number of nodes al

深藏阁楼爱情的钟/ 2022年04月22日 23:18/ 0 赞/ 28 阅读

相关 Maximum Depth of Binary Tree leetcode

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes a

Bertha 。/ 2022年01月09日 23:11/ 0 赞/ 313 阅读