559. N 叉树的最大深度-蒲公英云

559. N 叉树的最大深度

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

给定一个 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] 之间。

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));
}