LC543 - Diameter of Binary Tree

Problem

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

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].

Solution

We use a list as the variable passed in because Python makes a copy of primitive types passed into a function, so if you want to recursively access and modify res without having it as the return statement, we use a list which is pass by reference.

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
	def dfs(root, res):
		if not root:
			return 0
	
		left = dfs(root.left, res)
		right = dfs(root.right, res)
		res[0] = max(res[0], left + right)
	
		return max(left, right) + 1  
	
	res = [0]
	dfs(root, res)
	
	return res[0]