LeetCode 热题 100 543. 二叉树的直径

LeetCode 热题 100 | 543. 二叉树的直径

大家好，今天我们来解决一道经典的二叉树问题——二叉树的直径。这道题在 LeetCode 上被标记为简单难度，要求计算给定二叉树的直径。

问题描述

给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点。

示例 1：

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

示例 2：

输入：root = [1,2]
输出：1

提示：

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

解题思路

核心思想

1. 递归法：

   • 使用递归法计算每个节点的左子树和右子树的最大深度。
   • 对于每个节点，计算其左子树深度和右子树深度之和，作为该节点的直径。
   • 更新全局最大直径。

2. 辅助函数：

   • 定义一个辅助函数 maxDepth，用于计算以某个节点为根的子树的最大深度。

Python代码实现

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.max_diameter = 0
        
        def maxDepth(node: TreeNode) -> int:
            if not node:
                return 0
            left_depth = maxDepth(node.left)
            right_depth = maxDepth(node.right)
            # 更新全局最大直径
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            return max(left_depth, right_depth) + 1
        
        maxDepth(root)
        return self.max_diameter

代码解析

1. 初始化：

   • 定义一个全局变量 self.max_diameter，用于存储全局最大直径。

2. 递归函数：

   • 定义一个辅助函数 maxDepth，用于计算以某个节点为根的子树的最大深度。
   • 如果节点为空，返回 0。
   • 递归计算左子树和右子树的最大深度。
   • 更新全局最大直径为左子树深度和右子树深度之和。
   • 返回当前节点的最大深度。

3. 主函数：

   • 调用 maxDepth 函数，从根节点开始计算最大深度。
   • 返回全局最大直径。

复杂度分析

• 时间复杂度：O(n)，其中 n 是树中节点的数量。每个节点被访问一次。
• 空间复杂度：O(h)，其中 h 是树的高度。递归调用栈的深度最多为树的高度。

示例运行

示例 1

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

示例 2

输入：root = [1,2]
输出：1

总结

通过递归法，我们可以高效地计算二叉树的直径。递归函数 maxDepth 用于计算每个节点的左子树和右子树的最大深度，并更新全局最大直径。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！