N叉树的最大深度（559）

题目

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

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

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

示例

可视化树见559.N叉树的最大深度 - Leetcode (opens new window)

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

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

算法

广度优先遍历

因为是N叉树，所以我们每次推入队列queue的是当前节点的所有children

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
export const maxDepth = (root) => {
	if (!root) return 0;
	let dep = 0;
	let queue = [root];
	while (queue.length) {
		dep++;
		const len = queue.length;
		for (let i = 0; i < len; i++) {
			const curNode = queue.shift();
			if (curNode.children.length) {
				queue.push(...curNode.children);
			}
		}
	}
	return dep++;
};

深度优先遍历

维护两个变量分别表示当前深度curDep、最大深度maxDep

每次遍历到新节点时判断是不是curDep > maxDep，如果是，则更新maxDep

最后返回maxDep

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
export const maxDepth = (root) => {
	if (!root) return 0;
	let curDep = 1,
		maxDep = 1;
	const rec = (root, depth) => {
		maxDep = Math.max(maxDep, depth);
		if (root.children.length) {
			root.children.forEach((node) => rec(node, depth + 1));
		}
	};
	rec(root, curDep);
	return maxDep;
};