LeetCode 543 Diameter of Binary Tree

LeetCode

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10<sup>4</sup>]. -100 <= Node.val <= 100

题目大意：

求树的直径：任何两个节点的最大距离

解题思路：

DFS

解题步骤：

N/A

注意事项：

1. 三种情况：自己+左，自己+右，左+右，不要漏掉最后一种
2. 用nonlocal就不用定义self.max_len的全局变量

Python代码：

def diameterOfBinaryTree(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		left = dfs(root.left) + 1
		right = dfs(root.right) + 1
		res = max(left, right)
		total = left + right - 1
		max_len = max(res, total, max_len)
		return res

	dfs(root)
	return max_len - 1

算法分析：

时间复杂度为O(n)，空间复杂度O(1)