【leetcode.559】N叉树的最大深度

谁借莪１个温暖的怀抱￠ 2022-12-10 02:27 210阅读 0赞

一、题目描述

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

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

例如，给定一个 3叉树 :

5ac26bc1cec207a0bf63ddce393d6dc9.png

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

说明:

  1. 树的深度不会超过 1000。
  2. 树的节点总不会超过 5000。

二、思路

采用深度优先搜索，递归获取子节点的最大深度，接着更新maxRootDepth即可。

该方案的时间复杂度为O(N)，N代表节点总数，空间复杂度为O(1)。

  1. public int maxDepth(Node root) {
  2.         if (root == null) {
  3.             return 0;
  4.         }
  5.         if (root.children == null) {
  6.             return 1;
  7.         }
  8.         int rootMaxDepth = 0;
  9.         for (Node children : root.children) {
  10.             //递归获取子节点的最大深度
  11.             int childrenMaxDepth = maxDepth(children);
  12.             //更新max值
  13.             rootMaxDepth = Math.max(rootMaxDepth, childrenMaxDepth);
  14.         }
  15.         return rootMaxDepth + 1;
  16.     }

提交答案：

2020092314524584.png

发表评论

表情：
评论列表 （有 0 条评论，210人围观）

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

相关阅读

    相关 559. N 叉树的最大深度

    给定一个 N 叉树，找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

    灰太狼灰太狼/ 0 赞/ 81 阅读