題目

543. 二叉樹的直徑

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

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

兩節點之間路徑的 長度 由它們之間邊數表示。

題解

思路：找到左邊最長和右邊最長

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def diameterOfBinaryTree(self, root):""":type root: Optional[TreeNode]:rtype: int"""self.ans = 0def dfs(root):if root is None:return -1l_len = dfs(root.left) + 1r_len = dfs(root.right) + 1self.ans = max(self.ans, l_len + r_len)return max(l_len, r_len)dfs(root)return self.ans   

解釋

假設我們有以下的二叉樹：

     1/ \2   3/ \  4   5

步驟 1: 初始調用
diameterOfBinaryTree(root) 調用 dfs(root)，即傳入根節點 1。

步驟 2: 遞歸計算深度

• 對節點 1：

  • 左子樹：遞歸調用 dfs(root.left)，即節點 2。

• 對節點 2：

  • 左子樹：遞歸調用 dfs(root.left)，即節點 4。

    • 節點 4 是葉子節點，因此返回 0。

  • 右子樹：遞歸調用 dfs(root.right)，即節點 5。

    • 節點 5 是葉子節點，因此返回 0。

  • 對節點 2：l_len = 0 + 1 = 1，r_len = 0 + 1 = 1，self.ans = max(0, 1 + 1) = 2，返回 max(1, 1) = 1。

• 對節點 1：

  • 左子樹：返回節點 2 的深度 1。

  • 右子樹：遞歸調用 dfs(root.right)，即節點 3。

    • 節點 3 是葉子節點，因此返回 0。

  • 對節點 1：l_len = 1 + 1 = 2，r_len = 0 + 1 = 1，self.ans = max(2, 2 + 1) = 3，返回 max(2, 1) = 2。

步驟 3: 返回結果
最終返回 self.ans = 3，表示二叉樹的直徑為 3，即從節點 4 到節點 5，通過節點 2 再到節點 1，該路徑包含 3 個節點。