侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-17 / 0 评论 / 0 点赞 / 206 阅读 / 788 字
温馨提示:
本文最后更新于 2023-02-03,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1522. N 叉树的直径


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

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

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

示例 1:

image-20220517180556123

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

示例 2:

image-20220517180628393

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

示例 3:

image-20220517180612722

输入: 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(某个节点两个最高子树的高度和)max(某个节点两个最高子树的高度和),就可以把问题 “计算这棵树的直径长度” 转换为 “找到某个‘有两个高度最高的子树的高度加起来是最大的’的节点”,例如:

image-20220517182200559

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

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

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

评论区