[每日一题][找工作第33天][2025-10-25] Leetcode 543. 二叉树的直径

题目

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
 
示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
 
提示：

• 树中节点数目在范围 [1, 104] 内
• -100 <= Node.val <= 100

我的代码（Python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def calDiameter(self, root:  Optional[TreeNode]) -> (int, int):
        if not root:
            return (0, -1)
        lInnerD, lToRoot = self.calDiameter(root.left)
        rInnerD, rToRoot = self.calDiameter(root.right)
        return (max(lInnerD, rInnerD, lToRoot + rToRoot + 2), max(lToRoot, rToRoot) + 1)

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        maxD, _ = self.calDiameter(root)
        return maxD

点评

一般来说遇到树相关的问题，首先都会往递归方向考虑。
我遇到过几次递归调用栈溢出的情况，所以能不用递归尽量都不想用，尾递归优化也不是100%可靠的。
但是递归确实很方便，也容易考虑。
这题的基本思路很简单：左子树深度 + 右子树深度 + 2，这是连通左右子树的最大长度，和两个子树内部的最大路径长度比较取最大值就是直径。递归调用即可。
我这里思路是对的，但是浪费了空间：没有必要考虑每个子树的内部直径并返回缓存，像官方解法一样用一个变量缓存就可以了。
另外为也特殊处理端结点，我还用了-1来作为计算长度的起始值。看起来比较奇怪，不过结果是对的。

---

baddif@gmail.com

AI简历优化站

Nonpareil.me：优化简历，助力职场
开源代码

AI求职跟踪器（建设中）

开源代码

主站（建设中）

Nonpareil Me

相关平台

Github Issues / Notion / Blog