Given the root of a binary tree, return the length of its diameter: the number of edges on the longest path between any two nodes. The path does not have to go through the root.
Example 1
Input: root = [1,2,3,4,5]
Output: 3
The path 4, 2, 1, 3 (or 5, 2, 1, 3) has 3 edges.
Example 2
Input: root = [1,2]
Output: 1
Constraints
- The number of nodes is in the range 1 to 10^4
- -100 <= Node.val <= 100
Hints
Frequently asked at: Meta, Amazon, Google, Microsoft
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force computes, for every node, the heights of its two subtrees from scratch, which is O(n^2) on a skewed tree. Notice that the longest path "bends" at exactly one node, and its length there is leftHeight + rightHeight. A single post-order DFS already computes the height of every subtree, so while returning heights we can also check this sum at every node and keep the maximum.
Algorithm
- Keep a variable
best = 0. - Write
height(node): return 0 for null. - Compute
l = height(node.left)andr = height(node.right); setbest = max(best, l + r). - Return
1 + max(l, r). - Call
height(root)and returnbest.
Time:
O(n)Space: O(h) recursion depthInterview tip: The most common mistake is returning only
height(root.left) + height(root.right). The longest path may lie entirely inside one subtree, for example when the root has only one child and the long path bends lower down.class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: best = 0Β def height(node): # number of nodes on the longest downward path from node nonlocal best if not node: return 0 l, r = height(node.left), height(node.right) best = max(best, l + r) # longest path that bends at this node return 1 + max(l, r)Β height(root) return bestCtrl + Enter runs the examples