一、题目
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
二、示例
2.1> 示例 1：
【输入】root = [1,2,3,4,5]
【输出】3
【解释】3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
2.2> 示例 2：
【输入】root = [1,2]
【输出】1
提示：
- 树中节点数目在范围
[1, 10^4]内 -
-100<= Node.val <=100
三、解题思路
根据题目描述，我们要获得二叉树中任意两个节点的最大直径。那么如何确定哪两个节点是值得去进行计算的？或者那两个节点我们应该去进行计算。以一个3节点的子树为例，分为：根节点（rootNode）、左子节点（leftNode）和右子节点（rightNode），那么leftNode到rootNode的距离和rootNode到rightNode的距离其实没有必要参与最大直径的计算，因为leftNode到rightNode的距离一定倾向是最大直径。所以，我们得出一个结论：
可能的最大直径 = leftNode到rootNode的距离 + rootNode到rightNode的距离；
那么，因为二叉树也并不只有3个节点，如果节点很多的话，那么这个二叉树的层级也就会越深，那么下面我们其实如果能找到leftNode到rootNode距离的最大值（或最深路径）以及找到rootNode到rightNode距离的最大值（或最深路径），那么相加必然就是本题所要求解的最大直径了。
那么针对树形结构的解题，最常用的方式就是递归算法了，从叶子节点开始统计，一直统计到根节点，并且每次都要进行直径的计算和比较，当遍历到根节点时，最大直径也就计算出来了。
以上就是本题的解题思路，为了便于大家更加深入的理解，下面我们以输入root = [1,2,3,4,5]为例，看一下是如何进行最大直径计算的（图中省略了根节点的深度和直径的计算，大家自行脑补即可），请见下图所示：
四、代码实现
class Solution {
int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return diameter;
}
public int depth(TreeNode node) {
if (node == null) return 0;
int leftLen = depth(node.left); // node左子树最大深度
int rightLen = depth(node.right); // node右子树最大深度
diameter = Math.max(diameter, leftLen + rightLen); // 对比直径
return Math.max(leftLen, rightLen) + 1; // 获得最大深度
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
