题目
题目来源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; }