559. N 叉树的最大深度

2021-03-18

LeetCode

BFS

4 分钟读完 (大约 564 个字) 0次访问

leetcode 559. N 叉树的最大深度

题目：559. N 叉树的最大深度

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

方法：BFS（广度优先搜索）

思路：BFS（广度优先搜索），将子节点作为扩展方向，进行BFS搜索。

运行数据：执行用时：3 ms，内存消耗：38.7 MB

复杂度分析：

时间复杂度：O(n)，n为节点数。
空间复杂度：O(n)，n为节点数。

// LeetCode指定调用方法 
public int maxDepth(Node root) {
		
    // 记录深度
    int depth = 0;

    // 根节点为null，则直接返回深度0
    if (root == null) {
        return depth;
    }

    // 用于BFS的队列
    Queue<Node> queue = new LinkedList<>();

    // 将第一个数入队
    queue.offer(root);

    // 记录当前队列的长度，当队列为空时，BFS全部搜索结束（用以代替 queue.isEmpty() 增加每次循环判断时的效率）
    int queueLength = 1;

    // BFS
    while (queueLength > 0) {

        // 记录当前扩展轮的数的个数
        int currQueueLength = queueLength;

        // 扩展当前轮次的数
        while (currQueueLength-- > 0 ) {

            // 将队列中第一个数出队
            Node currNode = queue.poll();

            // 更新当前队列长度
            queueLength--;

            // 如果没有子节点，则跳过扩展
            if (currNode.children == null) {
                continue;
            }

            // 遍历子节点，扩展搜索
            for (Node node : currNode.children) {

                // 将扩展数入队
                queue.offer(node);

                // 更新当前队列长度
                queueLength++;
            }
        }

        // 更新深度
        depth++;
    }
    return depth;
}