【递归, DFS】N 叉树的直径

题目

1522. N 叉树的直径

---

给定一棵 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] 间。

解题

方法一：递归 DFS

思路

由题意可以把树的直径长度看作 $max(某个节点两个最高子树的高度和)$，就可以把问题 “计算这棵树的直径长度” 转换为 “找到某个‘有两个高度最高的子树的高度加起来是最大的’的节点”，例如：

如图该二叉树的直径可以看作两个黄色区域的子树的高度和+2。

具体做法是：遍历每一个节点，把它所有子树的高度计算出来放入集合，找出最高的两个高度，把它们加起来与当前树的直径作比较，维护一个最大的值。
又因为 $$一颗树的高度=max(所有子树的高度) + 1$$，所以可以使用深度优先遍历完成：

• 遍历到某个节点，如果该节点是叶子节点，直接返回高度 0。
• 否则，定义一个集合用于存放子树高度(depthList)。
• 遍历子节点集合，把每个子节点作为根节点递归地求高度，并放入 depthList。
• 遍历 depthList ，把最高的两个高度拿出来(max, secMax)。
• 如果 max + secMax 比 ans 大就更新 ans。
• 返回 $最大的高度 + 1$ 作为该树的高度。

代码

class Solution {
    private int ans = 0;

    public int diameter(Node root) {
        if (root == null) return 0;
        dfs(root);
        return ans;
    }

    private int dfs(Node root) {
        if (root.children == null) return 0;
        List<Integer> depthList = new ArrayList<>();
        for (Node child : root.children) {
            depthList.add(dfs(child));
        }
        int max = 0, secMax = 0;
        for (int depth : depthList) {
            if (depth > max) {
                secMax = max;
                max = depth;
            } else if (depth > secMax) {
                secMax = depth;
            }
        }
        ans = Math.max(ans, max + secMax);
        return max + 1;
    }
}

优化

在遍历子节点列表时同时维护最大子树高度和次大子树高度。

class Solution {
    private int ans = 0;

    public int diameter(Node root) {
        if (root == null) return 0;
        dfs(root);
        return ans;
    }

    private int dfs(Node root) {
        int maxDepth = 0;
        for (Node child : root.children) {
            int secMaxDepth = dfs(child);
            ans = Math.max(ans, maxDepth + secMaxDepth);
            maxDepth = Math.max(maxDepth, secMaxDepth);
        }
        return maxDepth + 1;
    }
}