二叉樹的直徑：樹中任意兩個節點間最長路徑的長度。這個路徑可能經過根節點，也可能不經過。

算法思路

采用深度優先搜索(DFS)的后序遍歷方式，計算每個節點的左右子樹高度，并在過程中更新最大直徑。

代碼解析

var diameterOfBinaryTree = function(root) {let ans = 0  // 用于記錄當前找到的最大直徑const dfs = (node) => {if (node === null) {return 0  // 空節點的高度為0}// 遞歸計算左右子樹的高度const lLen = dfs(node.left)const rLen = dfs(node.right)// 更新最大直徑：當前節點作為"轉折點"時的路徑長度ans = Math.max(ans, lLen + rLen)// 返回當前節點的高度（左右子樹中較高的那個 + 1）return Math.max(lLen, rLen) + 1}dfs(root)  // 從根節點開始遍歷return ans
};

關鍵點解釋

1. 后序遍歷：先處理左右子樹，再處理當前節點，這確保了在計算當前節點時，其子樹的信息已經計算完成。

2. 高度計算：對于每個節點，我們計算其左右子樹的高度：

   • lLen 是左子樹的高度
   • rLen 是右子樹的高度

3. 直徑更新：直徑是通過某個節點的最長路徑，這個路徑長度等于左子樹高度 + 右子樹高度。我們不斷用這個值更新全局最大值 ans。

4. 返回值：每個節點返回的是以它為根的子樹的高度，這是為了父節點能夠計算它自己的直徑。

示例分析

考慮以下二叉樹：

      1/ \2   3/ \     4   5    

計算過程：

1. 節點4：lLen=0, rLen=0 → ans=0, 返回1
2. 節點5：lLen=0, rLen=0 → ans=0, 返回1
3. 節點2：lLen=1(來自4), rLen=1(來自5) → ans=2, 返回2
4. 節點3：lLen=0, rLen=0 → ans=2, 返回1
5. 節點1：lLen=2(來自2), rLen=1(來自3) → ans=3, 返回3

最終直徑為3（路徑[4,2,1,3]或[5,2,1,3]的長度）

時間復雜度

• 時間復雜度：O(n)，其中n是樹中的節點數。每個節點只被訪問一次。
• 空間復雜度：O(h)，其中h是樹的高度。這是遞歸調用棧的空間消耗。