0543：二叉树的直径

力扣第 543 题

题目

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 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

分析

假设路径经过根节点 root，那么最大长度是 （终点为 root.left 的最大路径长度 + 终点为 root.right 的最大路径长度 + 2）。

为了递归，令辅助函数 help(node) 同时返回 node 的直径长度、向上的终点为 node 的最大路径长度。

再注意下边界条件即可。

解答

1
2
3
4
5
6
7
8

def diameterOfBinaryTree(self, root: TreeNode) -> int:
	def help(node):
		if not node:
			return -1, -1
		l0, l1 = help(node.left)
		r0, r1 = help(node.right)
		return max(l0, r0, l1+r1+2), 1+max(l1, r1)
	return help(root)[0]

52 ms