559. Maximum Depth of N-ary Tree(python+cpp)
题目:
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:
We should return its max depth, which is 3.Note: The depth of the tree is at most 1000. The total number of nodes
is at most 5000.
解释:
求二叉树的深度,用递归即可。
python代码:
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution(object):
def maxDepth(self, root):
"""
:type root: Node
:rtype: int
"""
if not root:
return 0
elif not root.children:
return 1
else:
return 1+max(map(self.maxDepth,root.children))
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==NULL)
return 0;
int maxValue=1;
for(int i=0;i<root->children.size();i++)
{
maxValue=max(1+maxDepth(root->children[i]),maxValue);
}
return maxValue;
}
};
总结:
一般树的题目都用递归求解。python的map()函数非常好用。