给定一棵 N 叉树的根节点 root ，计算这棵树的直径长度。

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

（N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）

 

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3
解释：直径如图中红线所示。

示例 2：

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

示例 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]
输出: 7

 

提示：

  • N 叉树的深度小于或等于 1000 。
  • 节点的总个数在 [0, 10^4] 间。
Related Topics
  • 树
  • 深度优先搜索

  • 👍 25
  • 👎 0

    • 深度优先搜索算法

    深度优先搜索算法，类似的题目有，
    剑指 Offer 68 – II. 二叉树的最近公共祖先

    1740. 找到二叉树中的距离

    基本都一样的题目。多做几遍练练手加深印象

    class Solution {

    int max = 0;

    public int diameter(Node root) {
        dfs(root,0);
        return max;
    }


    public 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;
    }
}