[Leetcode 559]N叉树的最大深度Maximum Depth of N-ary Tree DFS/BFS模板
题目
https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
N叉树的最大深度
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.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: 3
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: 5
思路
可以用BFS/DFS
BFS核心模板
Queue q=new LinkedList
q.add(初始点)
while(!q.isempty){
q=q.size();
for(int i=0;i cur=q.remove() 提出当前元素 广度优先遍历,不断加进新元素(q不为空时一直在while,为空时证明已经遍历完成) q.add(初始点附近符合要求的节点) 这里写遍历过程中想记录更改什么 代码 BFS DFS
public int maxDepth(Node root) {
//bfs
if (root==null)
return 0;
int depth=0;
Queue
int max_depth=0;
public int maxDepth(Node root) {
dfs(root,1);
return max_depth;
}
public void dfs(Node node,int curDepth){
if (node==null)
return;
max_depth=Math.max(max_depth,curDepth);
for (Node child:node.children){
dfs(child,curDepth+1);//每次depth+1
}
}