题目地址(559. N 叉树的最大深度)

https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/

题目描述

  1. 给定一个 N 叉树，找到其最大深度。
  3. 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
  5. N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
  9. 示例 1：
  11. 输入：root = [1,null,3,2,4,null,5,6]
  12. 输出：3
  15. 示例 2：
  17. 输入：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]
  18. 输出：5
  23. 提示：
  25. 树的深度不会超过 1000 。
  26. 树的节点数目位于 [0, 104] 之间。

前置知识


公司

  • 暂无

思路

本质上和求二叉树没有区别 知识判断的从左右节点 到 从儿子节点的列表中进行判断

关键点


代码

  • 语言支持：Java

Java Code:

  2. /*
  3. // Definition for a Node.
  4. class Node {
  5.     public int val;
  6.     public List<Node> children;
  8.     public Node() {}
  10.     public Node(int _val) {
  11.         val = _val;
  12.     }
  14.     public Node(int _val, List<Node> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  20. class Solution {
  21.         public int maxDepth(Node root) {
  22.             Queue<Node> queue = new LinkedList<>();
  23.             int num = 0;
  24.             if (root == null) {
  25.                 return num;
  26.             }
  27.             queue.offer(root);
  28.             while (!queue.isEmpty()) {
  29.                 int size = queue.size();
  30.                 while (size > 0) {
  31.                     Node poll = queue.poll();
  32.                     for (int i = 0; i < poll.children.size(); i++) {
  33.                         if (poll.children.get(i) != null) {
  34.                             queue.offer(poll.children.get(i));
  35.                         }
  36.                     }
  37.                     size--;
  38.                 }
  39.                 num++;
  40.             }
  41.             return num;
  42.         }
  43.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：559. N 叉树的最大深度 - 图1#card=math&code=O%28n%29&id=wx1uk)
  • 空间复杂度：559. N 叉树的最大深度 - 图2#card=math&code=O%28n%29&id=JIcPR)