网站运营培训学校,北京网站改版价格,沈阳工程就业信息网,WordPress菜单过滤器文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;N 叉树的最大深度
出处#xff1a;559. N 叉树的最大深度
难度
3 级
题目描述
要求
给定一个 N 叉树#xf… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题N 叉树的最大深度
出处559. N 叉树的最大深度
难度
3 级
题目描述
要求
给定一个 N 叉树返回其最大深度。
最大深度是从根结点到最远叶结点的最长路径上的结点数。
N 叉树在输入中按层序遍历序列化表示每组子结点由空值 null \texttt{null} null 分隔请参见示例。
示例
示例 1 输入 root [1,null,3,2,4,null,5,6] \texttt{root [1,null,3,2,4,null,5,6]} root [1,null,3,2,4,null,5,6] 输出 3 \texttt{3} 3
示例 2 输入 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] \texttt{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]} 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] 输出 5 \texttt{5} 5
数据范围
树中结点数目在范围 [0, 10 4 ] \texttt{[0, 10}^\texttt{4}\texttt{]} [0, 104] 内N 叉树的高度小于或等于 1000 \texttt{1000} 1000
解法一
思路和算法
如果 N 叉树为空则深度为 0 0 0。对于非空 N 叉树首先计算每个子树的最大深度子树最大深度的最大值加 1 1 1 即为 N 叉树的最大深度每个子树的最大深度可以使用同样的方式计算。因此可以使用深度优先搜索计算 N 叉树的最大深度。
计算 N 叉树的最大深度的过程是一个递归的过程递归的终止条件是 N 叉树为空此时 N 叉树的最大深度为 0 0 0。对于非空 N 叉树首先递归地计算每个子树的最大深度然后将子树最大深度的最大值加 1 1 1 即为 N 叉树的最大深度。
代码
class Solution {public int maxDepth(Node root) {if (root null) {return 0;}int childDepth 0;ListNode children root.children;for (Node child : children) {childDepth Math.max(childDepth, maxDepth(child));}return childDepth 1;}
}复杂度分析 时间复杂度 O ( m ) O(m) O(m)其中 m m m 是 N 叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( m ) O(m) O(m)其中 m m m 是 N 叉树的结点数。空间复杂度主要是递归调用的栈空间取决于 N 叉树的高度最坏情况下 N 叉树的高度是 O ( m ) O(m) O(m)。
解法二
思路和算法
也可以使用广度优先搜索计算 N 叉树的最大深度。
广度优先搜索需要使用队列存储待访问的结点初始时将根结点入队列。最简单的广度优先搜索的做法是每次将一个结点出队列然后将该结点的子结点入队列直到队列为空时遍历结束。
这道题需要计算 N 叉树的最大高度因此在广度优先搜索的过程中需要维护深度的信息实现和最简单的广度优先搜索有所不同。为了维护深度信息需要确保每一轮访问的结点为同一层的全部结点。
初始时队列内只有根结点是同一层的全部结点。每一轮访问结点之前需要首先得到队列内的元素个数此时队列内的元素为同一层的全部结点然后访问这些结点并将这些结点的子结点入队列。一轮访问结束之后当前层的全部结点都已经出队列并被访问此时队列内的元素为下一层的全部结点下一轮访问时即可访问下一层的全部结点。使用上述做法可以确保每一轮访问的结点为同一层的全部结点。
在确保每一轮访问的结点为同一层的全部结点的情况之下根据访问的总轮数即可得到 N 叉树的最大深度其中根结点的深度为 1 1 1。
代码
class Solution {public int maxDepth(Node root) {if (root null) {return 0;}int depth 0;QueueNode queue new ArrayDequeNode();queue.offer(root);while (!queue.isEmpty()) {depth;int size queue.size();for (int i 0; i size; i) {Node node queue.poll();ListNode children node.children;for (Node child : children) {queue.offer(child);}}}return depth;}
}复杂度分析 时间复杂度 O ( m ) O(m) O(m)其中 m m m 是 N 叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( m ) O(m) O(m)其中 m m m 是 N 叉树的结点数。空间复杂度主要是队列空间队列内元素个数不超过 n n n。
