Python树直径算法详解（小白也能轻松掌握树的最长路径计算）

解决思路

计算树的直径有一个经典且高效的算法，其核心思想是：

1. 从任意一个节点出发，进行深度优先搜索（DFS）或广度优先搜索（BFS），找到离它最远的节点 A。
2. 再从节点 A 出发，再次进行 DFS/BFS，找到离 A 最远的节点 B。
3. 那么 A 到 B 的路径长度就是树的直径。

不过，在编程竞赛或面试中，更常用的是基于递归的“一次遍历”方法，通过后序遍历计算每个子树的高度，并在过程中更新最大直径。

Python 实现：递归法求树直径

我们先定义一个简单的二叉树节点类：

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right

接下来是核心算法。我们使用一个全局变量（或非局部变量）来记录当前遇到的最大直径：

def diameterOfBinaryTree(root):    # 用于存储最大直径    max_diameter = 0    def depth(node):        nonlocal max_diameter        if not node:            return 0                # 递归计算左右子树的高度        left_depth = depth(node.left)        right_depth = depth(node.right)                # 当前节点作为根时，经过它的最长路径 = 左高 + 右高        current_diameter = left_depth + right_depth                # 更新全局最大直径        max_diameter = max(max_diameter, current_diameter)                # 返回当前节点的高度（用于上层递归）        return max(left_depth, right_depth) + 1    depth(root)    return max_diameter

代码解析

• depth(node) 函数返回以 node 为根的子树的高度。
• 在计算高度的同时，我们计算经过当前节点的最长路径（即左子树高度 + 右子树高度）。
• 用 max_diameter 记录所有节点中该值的最大者，这就是整棵树的直径。

这个算法的时间复杂度是 O(n)，其中 n 是树中节点的数量，因为我们只遍历每个节点一次。

测试示例

# 构建如下二叉树：#       1#      / \#     2   3#    / \#   4   5root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)print(diameterOfBinaryTree(root))  # 输出：3（路径为 4 -> 2 -> 1 -> 3 或 5 -> 2 -> 1 -> 3）

总结

通过本文，你已经掌握了如何用 Python 实现树的最长路径（即树的直径）的计算。无论是面试题还是实际项目中的图论算法Python实现，这个技巧都非常实用。记住，关键在于理解“每个节点的直径 = 左子树高度 + 右子树高度”，并通过一次遍历完成计算。

希望这篇关于Python树直径算法的教程对你有帮助！动手写一写代码，加深理解吧。