Diameter of Binary 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.
Constraints:
- The number of nodes in the tree is in the range [1, 10^4].
- 1 <= Node.val <= 10^5
Examples:
Input: [1,2,3,4,5]
Output: 3
Explanation: The diameter is the path [4,2,1,3] or [5,2,1,3].
Solutions
Depth-First Search
Time: O(N)Space: O(H)
We use a depth-first search to calculate the height of each subtree and update the maximum diameter found so far.
class Solution:
def diameterOfBinaryTree(self, root:
TreeNode) -> int:
self.max_diameter = 0
def dfs(node):
if not node:
return 0
left_height = dfs(node.left)
right_height = dfs(node.right)
self.max_diameter = max(self.max_diameter, left_height + right_height)
return max(left_height, right_height) + 1
dfs(root)
return self.max_diameterFollow-up:
What if the tree is not binary?
