LeetCode 题解工作台
二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1： 输入： root = [1,2,3,4,5] 输出： 3 解释： 3 ，取路径 [4,…
3
题型
9
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们可以枚举二叉树的每个节点，以该节点为根节点，计算其左右子树的最大深度 和 ，则该节点的直径为 $\textit{l} + \textit{r}$。取所有节点的直径的最大值即为二叉树的直径。 时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2] 输出：1
提示：
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
解题思路
方法一：枚举 + DFS
我们可以枚举二叉树的每个节点，以该节点为根节点，计算其左右子树的最大深度 和 ，则该节点的直径为 。取所有节点的直径的最大值即为二叉树的直径。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def dfs(root):
if root is None:
return 0
nonlocal ans
left, right = dfs(root.left), dfs(root.right)
ans = max(ans, left + right)
return 1 + max(left, right)
ans = 0
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understand the relationship between subtree height and the diameter at each node.
- question_mark
Ability to optimize tree traversal to avoid redundant computations.
- question_mark
Demonstrate clarity in balancing between height calculation and tracking the diameter.
常见陷阱
外企场景- error
Forgetting to update the global diameter variable during traversal.
- error
Confusing the number of nodes in the path with the number of edges.
- error
Overcomplicating the problem by considering all possible paths instead of focusing on subtree heights.
进阶变体
外企场景- arrow_right_alt
Find the diameter of a binary tree with different constraints, like skewed trees or highly unbalanced trees.
- arrow_right_alt
Extend the problem to return the nodes involved in the longest path.
- arrow_right_alt
Optimize the solution by minimizing recursion depth for extremely large trees.