1522. N 叉树的直径 🔒

🟠   🔖  树 深度优先搜索  🔗 力扣 LeetCode

题目

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

Example 1:

Input: root = [1,null,3,2,4,null,5,6]

Output: 3 Explanation: Diameter is shown in red color.

Example 2:

Input: root = [1,null,2,null,3,4,null,5,null,6]

Output: 4 Example 3:

Input: 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]

Output: 7

Constraints:

• The depth of the n-ary tree is less than or equal to 1000.
• The total number of nodes is between [0, 10^4].

题目大意

给你一棵 N 叉树的根节点，返回该树的 直径 。

N 叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

N 叉树的输入序列化以其层序遍历表示，每层之间由 null 分隔。

解题思路

这题类似 第 543 题 二叉树的直径 ，二叉树的直径，就是左右子树的最大深度之和，那么直接的想法是对每个节点计算左右子树的最大高度，得出每个节点的直径，从而得出最大的那个直径。

同理 N 叉树的直径，可以使用递归来遍历树的每个节点，并记录以每个节点为根的子树的最大深度和次大深度。直径就是这两个深度之和。

需要灵活运用树的后序遍历，在 maxDepth 的后序遍历位置顺便计算最大直径。

代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameter = (root) => {
	if (!root) return 0;
	let res = 0;

	const maxDepth = (root) => {
		// 如果节点为空，深度为0
		if (!root) return 0;

		// 记录当前节点的最大深度和次大深度
		let max_depth = 0;
		let second_max_depth = 0;

		// 遍历子节点
		for (let i of root.children) {
			let depth = maxDepth(i);
			if (depth > max_depth) {
				second_max_depth = max_depth;
				max_depth = depth;
			} else if (depth > second_max_depth) {
				second_max_depth = depth;
			}
		}
		// 更新直径
		res = Math.max(max_depth + second_max_depth, res);

		// 返回当前节点的深度
		return max_depth + 1;
	};
	maxDepth(root);
	return res;
};

相关题目

题号	标题	题解	标签	难度
543	二叉树的直径	[✓]	树 深度优先搜索 二叉树