1522. Diameter of N-Ary Tree

🟠   🔖  树 深度优先搜索  🔗 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. 二叉树的直径
• 2246. 相邻字符不同的最长路径

- [543. 二叉树的直径](./0543.md)
- [2246. 相邻字符不同的最长路径](https://leetcode.com/problems/longest-path-with-different-adjacent-characters)