二叉树的直径

🟢 Easy · 🏷️ 树、递归、DFS · LeetCode#543

📖 题目

求二叉树里任意两个节点之间最长路径的边数，这条路径不一定经过根节点。

💡 思路

直径等于某个节点的"左子树深度 + 右子树深度"，但这个"某个节点"可以是树上任何一个节点，不一定是根——只在根节点算一次是不够的：

# ❌ 只检查了根节点，漏掉了别的节点可能构成更长的路径
d = depth(root.left) + depth(root.right)

正确做法是复用求深度的递归，但让每个节点在被访问到的时候都顺便检查一次自己的"左深度+右深度"，用一个全局变量记录出现过的最大值：

# ✅ depth 函数递归到每个节点时都检查一次
self.max_d = max(self.max_d, left + right)

💻 代码

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_d = 0
        self.depth(root)
        return self.max_d

    def depth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = self.depth(root.left)
        right = self.depth(root.right)
        self.max_d = max(self.max_d, left + right)   # 每个节点都检查
        return max(left, right) + 1

时间复杂度 O(n)，空间复杂度 O(h)，h 是树高。这种"用 self 存全局最优解，递归过程中顺手更新"的写法，遇到"求全树最优"类问题会经常用到。