559. Maximum Depth of N-ary Tree

深藏阁楼爱情的钟 2022-04-22 23:18 29阅读 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 条评论，29人围观）

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

相关阅读

相关 LeetCode - Easy - 559. Maximum Depth of N-ary Tree

Topic Tree Depth-first Search Breadth-first Search Description [https://

清疚/ 2022年10月06日 00:50/ 0 赞/ 14 阅读

相关 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 赞/ 25 阅读

相关 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 赞/ 25 阅读

相关 #104 Maximum Depth of Binary Tree

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

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

相关 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 赞/ 172 阅读

相关 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 赞/ 194 阅读

相关 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 赞/ 274 阅读

相关 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 赞/ 30 阅读

相关 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 赞/ 333 阅读

相关 maximum-depth-of-binary-tree

/\\ \ @author gentleKay \ 题目描述 \ Given a binary tree, find its maximum depth. \

àì夳堔傛蜴生んèń/ 2021年11月09日 08:42/ 0 赞/ 178 阅读