543.二叉树的直径
-
给你一棵二叉树的根节点，返回该树的直径。
-
二叉树的直径是指树中任意两个节点之间最长路径的长度 。这条路径可能经过也可能不经过根节点 root 。
-
两节点之间路径的长度由它们之间边数表示。
1. DFS（递归）
- 思路:
-
递归：使用递归来遍历树。对于每个节点，计算其左子树和右子树的深度，然后更新直径
-
深度计算：在递归过程中，计算每个节点的左子树和右子树的深度。深度是指从当前节点到叶子节点的最长路径的边数
-
更新直径：在递归过程中，直径可能是左子树的深度加上右子树的深度，需要不断更新这个值
-
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def diameterOfBinaryTree(self, root):""":type root: Optional[TreeNode]:rtype: int"""# 定义一个全局变量来存储直径self.diameter = 0def depth(node):if not node:return 0# 递归计算左子树和右子树的深度left_depth = depth(node.left)right_depth = depth(node.right)# 更新直径self.diameter = max(self.diameter, left_depth + right_depth)# 返回当前节点的深度return max(left_depth, right_depth) + 1depth(root)# 返回树的直径return self.diameter
-
代码说明
-
全局变量self.diameter：用于在递归过程中记录当前的最大直径
-
递归函数depth：计算每个节点的深度，并在递归过程中更新直径
-
直径更新：self.diameter = max(self.diameter, left_depth + right_depth)，确保每次递归都更新直径
-
返回值：depth函数返回当前节点的深度，而diameterOfBinaryTree返回最终的直径
-
-
时间复杂度：O(n)，n是节点个数
-
空间复杂度： O(h)，h是树的高度
2. BFS
- 思路：
从任意一个节点（根节点）出发，使用 BFS 找到离它最远的节点 A，再从节点 A出发，再次使用 BFS 找到离 A最远的节点 B，节点 A和B之间的路径就是树的直径。
from collections import dequeclass Solution(object):def diameterOfBinaryTree(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0# 辅助函数：BFS 找到离某个节点最远的节点def bfs_farthest_node(start_node):queue = deque([(start_node, 0)]) # (节点, 距离)visited = {start_node: None} # 记录父节点farthest_node = start_nodemax_distance = 0while queue:node, distance = queue.popleft()if distance > max_distance:max_distance = distancefarthest_node = node# 遍历左右子节点for neighbor in [node.left, node.right]:if neighbor and neighbor not in visited:visited[neighbor] = nodequeue.append((neighbor, distance + 1))return farthest_node, max_distance, visited# 第一次 BFS：找到离根节点最远的节点 Anode_A, _, _ = bfs_farthest_node(root)# 第二次 BFS：找到离节点 A 最远的节点 Bnode_B, diameter, _ = bfs_farthest_node(node_A)return diameter
- 代码说明：
- bfs_farthest_node 函数：使用BFS遍历树，找到离起始节点最远的节点。返回最远节点、最大距离以及每个节点的父节点信息
- 第一次BFS：从根节点出发，找到离根节点最远的节点A
- 第二次BFS：从节点A出发，找到离A最远的节点B，节点A和B之间的距离就是树的直径
- 时间复杂度：O(n)，n是节点个数
- 空间复杂度： O(n)
