当前位置：首页 > article >正文

leetcode_二叉树 543.二叉树的直径

article 2025/2/25 16:37:21

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 = 0

        def 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) + 1
       
        depth(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 deque

class 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_node
            max_distance = 0
            
            while queue:
                node, distance = queue.popleft()
                if distance > max_distance:
                    max_distance = distance
                    farthest_node = node
                
                # 遍历左右子节点
                for neighbor in [node.left, node.right]:
                    if neighbor and neighbor not in visited:
                        visited[neighbor] = node
                        queue.append((neighbor, distance + 1))
            
            return farthest_node, max_distance, visited
        
        # 第一次 BFS：找到离根节点最远的节点 A
        node_A, _, _ = bfs_farthest_node(root)
        
        # 第二次 BFS：找到离节点 A 最远的节点 B
        node_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)

查看全文

http://www.kler.cn/a/560566.html