2024/5/25 陰天。這幾天睡眠質量都非常好，一切似乎都在慢慢上升。先把題做了

1、題目描述

2、邏輯分析

題目要求就是給一個二叉樹，求出兩個節點之間的最大長度即為二叉樹的直徑。怎么做呢？我想不出來。看一下題解吧。題解給出的解法是深度優先搜索。我們來看看大致思路：

比如我們示例1給出的二叉樹：我們知道[4,2,1,3]和[5,2,1,3]是最大長度即直徑。那么我們可以將根節作為起點，搜索左邊的兒子和右邊的兒子，左邊長度記為L，右邊長度記為R。左邊可以搜出[4,2]和[5,2]，右邊可以搜出[3]。那么最大長度為L + R + 1，即為max，而最終的直徑為max - 1。遞歸找出最大的那個即為最終結果，下面看代碼

3、代碼演示

// 用于記錄二叉樹的直徑int maxd ;public int diameterOfBinaryTree(TreeNode root) {// 初始化 maxd 為 1,因為至少有一個節點maxd = 1;// 調用 depth 函數計算樹的深度,同時更新 maxd 的值depth(root);// 返回最大直徑,即 maxd - 1return maxd - 1;}public int depth(TreeNode root ){// 如果當前節點為空,返回 0if(root == null){return 0;}// 遞歸計算左子樹的深度int L = depth(root.left);// 遞歸計算右子樹的深度int R = depth(root.right);// 更新 maxd 的值,取當前最大值和 L + R + 1 中的最大值maxd = Math.max(maxd, L + R + 1);// 返回當前節點的深度,即左右子樹深度的最大值加 1return Math.max(L , R ) + 1;}

在IDE中運行一遍就順暢了許多，遞歸這一思想真的很重要。時間復雜度：O(n)，空間復雜度：O(height)，height為樹的高度。

ok，做完啦，再見！