一、題目

給你一棵二叉樹的根節(jié)點，返回該樹的 直徑 。

二叉樹的 直徑 是指樹中任意兩個節(jié)點之間最長路徑的 長度 。這條路徑可能經(jīng)過也可能不經(jīng)過根節(jié)點 root 。

兩節(jié)點之間路徑的 長度 由它們之間邊數(shù)表示。

二、示例

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

提示：

• 樹中節(jié)點數(shù)目在范圍 [1, 10^4] 內(nèi)
• -100 <= Node.val <= 100

三、解題思路

根據(jù)題目描述，我們要獲得二叉樹中任意兩個節(jié)點的最大直徑。那么如何確定哪兩個節(jié)點是值得去進(jìn)行計算的？或者那兩個節(jié)點我們應(yīng)該去進(jìn)行計算。以一個3節(jié)點的子樹為例，分為：根節(jié)點（rootNode）、左子節(jié)點（leftNode）和右子節(jié)點（rightNode），那么leftNode到rootNode的距離和rootNode到rightNode的距離其實沒有必要參與最大直徑的計算，因為leftNode到rightNode的距離一定傾向是最大直徑。所以，我們得出一個結(jié)論：

可能的最大直徑 = leftNode到rootNode的距離 + rootNode到rightNode的距離；

那么，因為二叉樹也并不只有3個節(jié)點，如果節(jié)點很多的話，那么這個二叉樹的層級也就會越深，那么下面我們其實如果能找到leftNode到rootNode距離的最大值（或最深路徑）以及找到rootNode到rightNode距離的最大值（或最深路徑），那么相加必然就是本題所要求解的最大直徑了。

那么針對樹形結(jié)構(gòu)的解題，最常用的方式就是遞歸算法了，從葉子節(jié)點開始統(tǒng)計，一直統(tǒng)計到根節(jié)點，并且每次都要進(jìn)行直徑的計算和比較，當(dāng)遍歷到根節(jié)點時，最大直徑也就計算出來了。

以上就是本題的解題思路，為了便于大家更加深入的理解，下面我們以輸入root = [1,2,3,4,5]為例，看一下是如何進(jìn)行最大直徑計算的（圖中省略了根節(jié)點的深度和直徑的計算，大家自行腦補即可），請見下圖所示：

四、代碼實現(xiàn)

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;
 *     }
 * }
 */

今天的文章內(nèi)容就這些了：

寫作不易，筆者幾個小時甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點贊 & 分享 。

更多技術(shù)干貨，歡迎大家關(guān)注公眾號“爪哇繆斯” ~ \(^o)/ ~ 「干貨分享，每天更新」