LeetCode 1522. N 叉树的直径

题目描述

给定一棵 N 叉树的根节点 root ，计算这棵树的直径长度。
N 叉树的直径指的是树中任意两个节点间路径中 最长 路径的长度。这条路径可能经过根节点，也可能不经过根节点。
（N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）
  示例 1：
  输入：root = [1,null,3,2,4,null,5,6]
  输出：3

LeetCode 1522. N 叉树的直径
提示：

    N 叉树的深度小于或等于 1000 。节点的总个数在 [0, 10^4] 间。

一、解题关键词

二、解题报告

1.思路分析

2.时间复杂度

3.代码示例

class Solution {int max = 0;public int diameter(Node root) {dfs(root,0);return max;}int dfs(Node node,int deep){if(node == null) return deep - 1;int childMaxDeep = deep;int max1 = 0;int max2 = 0;for(Node child : node.children){int childDeep = dfs(child,deep + 1);childMaxDeep = Math.max(childMaxDeep,childDeep);if(childDeep > max1){max2 = max1;max1 = childDeep;}else if(childDeep > max2){max2 = childDeep;}}max = Math.max(max,max1 + max2 -deep -deep);return childMaxDeep;}
}

2.知识点

递归计算 、DFS

---

总结

相同题目

xxx