leetcoded 559. N 叉树的最大深度

[wangyewei]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree

[wangyewei]

思路和算法
深度优先搜索
dfs

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0 
    let maxChildDepth = 0
    const {children} = root
    for(const child of children) {
        const childrenDepth = maxDepth(child)
        maxChildDepth = Math.max(maxChildDepth, childrenDepth)
    }
    return maxChildDepth + 1
};

复杂度分析

• 时间复杂度：O(n)其中n为子节点数
• 空间复杂度：O(height)其中height为树的深度

[wangyewei]

思路和算法
广度优先搜索
计算出树的层数即可

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0
    let queue = [ root ]
    let depth = 0
    while(queue.length) {
        let length = queue.length
        while(length--) {
            const node = queue.shift()
            node.children && (queue = queue.concat(node.children))
        }
        depth++
    }
    return depth
};

复杂度分析

• 时间复杂度：O(n)其中n为子节点数
• 空间复杂度分析： 最坏的情况下为O(n)