LeetCode热题100-二叉树的直径

给你一棵二叉树的根节点返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。示例 1输入root [1,2,3,4,5]输出3解释3 取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。核心思路某节点为最高点的最长路径 左子树深度 右子树深度全局直径 遍历所有节点取上述值的最大值后序遍历先求左右深度再更新全局最大直径class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.max_len 0 def dfs(node): if not node: return 0 left_depth dfs(node.left) right_depth dfs(node.right) self.max_len max(self.max_len, left_depth right_depth) return max(left_depth, right_depth) 1 dfs(root) return self.max_len