559. N 叉树的最大深度

灰太狼 2023-10-04 09:04 78阅读 0赞

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

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

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

**示例 1：**

![042aa242e9be82786f7906e8d95631bb.png][]

输入：root = [1,null,3,2,4,null,5,6]
    输出：3

**示例 2：**

![481a463e68315c2a1a14ec0d9522c4dd.png][]

输入：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]` 之间。

package Solution559;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    class Node {
    	public int val;
    	public List<Node> children;
    
    	public Node() {
    	}
    
    	public Node(int _val) {
    		val = _val;
    	}
    
    	public Node(int _val, List<Node> _children) {
    		val = _val;
    		children = _children;
    	}
    }
    
    class Solution {
    
    	public int maxDepth(Node root) {
    		if (root == null)
    			return 0;
    		int max = 0;
    		for (Node n : root.children) {
    			if (n != null) {
    				max = Math.max(max, maxDepth(n));
    			}
    		}
    		return max + 1;
    	}
    
    	public static void main(String[] args) {
    		Solution sol = new Solution();
    
    		Node node5 = new Node(5);
    		node5.children = new ArrayList<>();
    		Node node6 = new Node(6);
    		node6.children = new ArrayList<>();
    		Node node3 = new Node(3);
    
    		node3.children = new ArrayList<>();
    		node3.children.add(node5);
    		node3.children.add(node6);
    
    		Node node2 = new Node(2);
    		node2.children = new ArrayList<>();
    		Node node4 = new Node(4);
    		node4.children = new ArrayList<>();
    		Node node1 = new Node(1);
    
    		node1.children = new ArrayList<>();
    		node1.children.add(node3);
    		node1.children.add(node2);
    		node1.children.add(node4);
    
    		System.out.println(sol.maxDepth(node1));
    	}
    
    }

package Solution559b;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    class Node {
    	public int val;
    	public List<Node> children;
    
    	public Node() {
    	}
    
    	public Node(int _val) {
    		val = _val;
    	}
    
    	public Node(int _val, List<Node> _children) {
    		val = _val;
    		children = _children;
    	}
    }
    
    class Solution {
    
    	public int maxDepth(Node root) {
    		int level = 0;
    		if (root == null)
    			return level;
    		Queue<Node> queue = new LinkedList<Node>();
    		queue.offer(root);
    		while (!queue.isEmpty()) {
    			int size = queue.size();
    			for (int i = 0; i < size; i++) {
    				Node tmp = queue.poll();
    				for (int j = 0; j < tmp.children.size(); j++)
    					queue.offer(tmp.children.get(j));
    			}
    			level++;
    		}
    		return level;
    	}
    
    	public static void main(String[] args) {
    		Solution sol = new Solution();
    
    		Node node5 = new Node(5);
    		node5.children = new ArrayList<>();
    		Node node6 = new Node(6);
    		node6.children = new ArrayList<>();
    		Node node3 = new Node(3);
    
    		node3.children = new ArrayList<>();
    		node3.children.add(node5);
    		node3.children.add(node6);
    
    		Node node2 = new Node(2);
    		node2.children = new ArrayList<>();
    		Node node4 = new Node(4);
    		node4.children = new ArrayList<>();
    		Node node1 = new Node(1);
    
    		node1.children = new ArrayList<>();
    		node1.children.add(node3);
    		node1.children.add(node2);
    		node1.children.add(node4);
    
    		System.out.println(sol.maxDepth(node1));
    	}
    
    }

[042aa242e9be82786f7906e8d95631bb.png]: https://img-blog.csdnimg.cn/img_convert/042aa242e9be82786f7906e8d95631bb.png
[481a463e68315c2a1a14ec0d9522c4dd.png]: https://img-blog.csdnimg.cn/img_convert/481a463e68315c2a1a14ec0d9522c4dd.png