LeetCode 543. 二叉树的直径

文章目录

• 前言
• 题目
• 题解
• NO1：深搜（统计最大直径）
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：543. 二叉树的直径，难度：简单。

题目描述(摘自leetcode)：

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

---

题解

NO1：深搜（统计最大直径）

直径指的是某个节点的左右节点深度之和。

①1的直径长度为1+2=3，左右深度之和。

②2的直径长度为1+1=2，依旧是左右两边的深度之和。

也就是说我们最终要找到指定某个节点的最大直径长度！

思路：使用深搜，思路与统计二叉树的深度一致，只不过在本题中是要求得二叉树的最大直径，那么在递归过程中需要不断计算左右节点深度之和的最大值，也就是说整个递归都是找到最大值所服务的。

代码：时间复杂度O(n)，空间复杂度(Ologn)：使用递归dfs这里树的深度即为空间复杂度

class Solution {
    
    private int max;

    public int diameterOfBinaryTree(TreeNode root) {
        getMaxDepth(root);
        return max;
    }

    private int getMaxDepth(TreeNode root){
        if (root == null) {
            return 0;
        }
        //左边最大深度
        int l = getMaxDepth(root.left);
        //右边最大的深度
        int r = getMaxDepth(root.right);
        //若是该节点的左右节点的深度之和>max，则更新最大的深度值
        if ((l + r) > max) {
            max = l + r;
        }
        return Math.max(l, r) + 1;
    }
}

---

参考文章

[1]. leetcode题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.12