当前位置：网站首页>leetcode刷题：二叉树08（N叉树的最大深度）

leetcode刷题：二叉树08（N叉树的最大深度）

2022-07-04 03:51:00 【涛涛英语学不进去】

559.n叉树的最大深度

力扣题目链接

给定一个 n 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如，给定一个 3叉树 :

559.n叉树的最大深度

我们应返回其最大深度，3。

其实一样的，层序遍历即可。

package com.programmercarl.tree;

import java.util.ArrayDeque;
import java.util.Deque;

/** * @ClassName MaxDepth2 * @Descriotion TODO * @Author nitaotao * @Date 2022/7/3 22:24 * @Version 1.0 * 559. N 叉树的最大深度 * https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/ **/
public class MaxDepth2 {
    
    public int maxDepth(Node root) {
    
        int maxDepth = 0;
        if (root == null) {
    
            return maxDepth;
        }
        Deque<Node> deque = new ArrayDeque<Node>();
        //层次遍历当前树，一层深度+1
        deque.offer(root);
        while (!deque.isEmpty()) {
    
            //这句话是核心， size是控制每层有多少元素的变量
            int size = deque.size();
            maxDepth++;
            while (size > 0) {
    
                root = deque.poll();
                for (Node item : root.children) {
    
                    deque.offer(item);
                }
                size--;
            }
        }
        return maxDepth;
    }
}