题目
题目来源leetcode
leetcode地址：559. N 叉树的最大深度，难度：简单。
题目描述(摘自leetcode)：
给定一个 N 叉树，找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。 示例 1： 输入：root = [1,null,3,2,4,null,5,6] 输出：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] 输出：5 提示： 树的深度不会超过 1000 。 树的节点数目位于 [0, 104] 之间。
题解
NO1：递归
思路：通过递归来求取最大的深度。
代码：
private int maxDepth; public int maxDepth(Node root) { recursionDepth(root,0); return maxDepth; } public void recursionDepth(Node root,int depth){ if(root == null){ return; } depth++; if(maxDepth<depth){ maxDepth = depth; } for (Node child : root.children) { recursionDepth(child,depth); } }
精简下代码：
public int maxDepth(Node root) { if (root == null) { return 0; } int depth = 0; for (Node child : root.children) { depth = Math.max(depth, maxDepth(child));//比较得到该层下方的最大深度 } return depth + 1; }
NO2：迭代（队列）
思路：迭代遍历方式，过程中计算一下深度。
代码：
//迭代（使用队列） public int maxDepth(Node root) { if (root == null) { return 0; } Deque<Node> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while (!queue.isEmpty()) { depth++; int size = queue.size(); while (size > 0) { Node node = queue.poll(); for (Node child : node.children) { if (child != null) { queue.offer(child); } } size--; } } return depth; }
