给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2] 输出：1
提示：
-
树中节点数目在范围
[1, 104]内 -
-100 <= Node.val <= 100
这道题就是一个深度优先搜索。不同之处在于，要在遍历过程中，把直径的最大值保存下来。同时，还要返回子树中最长的路径。
当节点为 Null 时，不返回 0 而返回其他值，也许含义更通顺。
|
Tip
|
这道题求解的是“路径长度”，不是节点数量。理解这一点就能理解为什么在 Null 节点返回 -1，到上一层节点（也就是叶子节点）再 +1，叶子节点最终返回 0。
|
- 一刷
-
link:{sourcedir}/_0543_DiameterOfBinaryTree.java[role=include] - 二刷
-
link:{sourcedir}/_0543_DiameterOfBinaryTree_2.java[role=include]