二叉树的直径

本文讲解 LeetCode 543 题“二叉树的直径”，通过递归求深度并更新全局最大值，给出清晰 Python 解法。

Leetcode Python 二叉树递归

阅读要点

直径定义为任意两节点路径长度的最大值。
经过某节点的最长路径 = 左子树深度 + 右子树深度。
使用递归求深度，并更新全局最大值。

题目

543. 二叉树的直径 - 力扣（LeetCode）

解法

对于经过某一节点的路径而言，其最长的路径为该节点的左子树深度加上右子树深度。例如，考虑一个节点，其左子树深度为 2，右子树深度为 3，那么经过该节点的最长路径长度为 5。因此，我们只需要遍历所有节点，计算每个节点的左右子树深度之和，并取最大值，即可得到整棵树的直径。

求深度的问题，我们在 104. 二叉树的最大深度 - 力扣（LeetCode）中已经解决，使用递归即可：

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

在本题中，我们可以在递归计算深度的同时，更新一个全局变量 res 来记录当前最大的左右子树深度之和。这样，当递归遍历完整棵树后，res 就是二叉树的直径。

具体解法如下：

答案

# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.res = 0
        # 返回该节点的最大深度
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.res = max(self.res, left + right)
            return max(left, right) + 1
        dfs(root)
        return self.res

复杂度分析：时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(h)，h 为树的高度，递归栈的深度。