一栏笆、題目
給你一棵二叉樹的根節(jié)點(diǎn)朽合，返回該樹的 直徑 鉴裹。
二叉樹的 直徑 是指樹中任意兩個(gè)節(jié)點(diǎn)之間最長路徑的 長度 。這條路徑可能經(jīng)過也可能不經(jīng)過根節(jié)點(diǎn) root 廷没。
兩節(jié)點(diǎn)之間路徑的 長度 由它們之間邊數(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é)點(diǎn)數(shù)目在范圍
[1, 10^4]內(nèi) -
-100<= Node.val <=100
三、解題思路
根據(jù)題目描述狭归，我們要獲得二叉樹中任意兩個(gè)節(jié)點(diǎn)的最大直徑夭坪。那么如何確定哪兩個(gè)節(jié)點(diǎn)是值得去進(jìn)行計(jì)算的？或者那兩個(gè)節(jié)點(diǎn)我們應(yīng)該去進(jìn)行計(jì)算过椎。以一個(gè)3節(jié)點(diǎn)的子樹為例室梅，分為：根節(jié)點(diǎn)（rootNode）、左子節(jié)點(diǎn)（leftNode）和右子節(jié)點(diǎn)（rightNode）疚宇，那么leftNode到rootNode的距離和rootNode到rightNode的距離其實(shí)沒有必要參與最大直徑的計(jì)算竞惋，因?yàn)?code>leftNode到rightNode的距離一定傾向是最大直徑。所以灰嫉，我們得出一個(gè)結(jié)論：
可能的最大直徑 = leftNode到rootNode的距離 + rootNode到rightNode的距離拆宛；
那么，因?yàn)槎鏄湟膊⒉恢挥?個(gè)節(jié)點(diǎn)讼撒，如果節(jié)點(diǎn)很多的話浑厚，那么這個(gè)二叉樹的層級也就會(huì)越深，那么下面我們其實(shí)如果能找到leftNode到rootNode距離的最大值（或最深路徑）以及找到rootNode到rightNode距離的最大值（或最深路徑）根盒，那么相加必然就是本題所要求解的最大直徑了钳幅。
那么針對樹形結(jié)構(gòu)的解題，最常用的方式就是遞歸算法了炎滞，從葉子節(jié)點(diǎn)開始統(tǒng)計(jì)敢艰，一直統(tǒng)計(jì)到根節(jié)點(diǎn)，并且每次都要進(jìn)行直徑的計(jì)算和比較册赛，當(dāng)遍歷到根節(jié)點(diǎn)時(shí)钠导，最大直徑也就計(jì)算出來了震嫉。
以上就是本題的解題思路，為了便于大家更加深入的理解牡属，下面我們以輸入root = [1,2,3,4,5]為例票堵，看一下是如何進(jìn)行最大直徑計(jì)算的（圖中省略了根節(jié)點(diǎn)的深度和直徑的計(jì)算，大家自行腦補(bǔ)即可）逮栅，請見下圖所示：
四悴势、代碼實(shí)現(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)容就這些了：
寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章措伐，只愿換來您幾秒鐘的 點(diǎn)贊 & 分享 特纤。
更多技術(shù)干貨，歡迎大家關(guān)注公眾號“爪哇繆斯” ~ \(o)/ ~ 「干貨分享侥加，每天更新」
