Diameter of Binary Tree
Given the root of a binary tree, return the length of its diameter: the length of the longest path between any two nodes. The path may or may not pass through the root. The length is the number of edges on the path.
Constraints:
- The number of nodes is in the range
[1, 10^4]. -100 <= Node.val <= 100
Intuition
1 12 / \3 2 34 / \ \5 4 5 6The longest path here is 4 to 2 to 1 to 3 to 6 with 4 edges (5 to 2 to 1 to 3 to 6 is the same length). Every path has a highest node where it turns. For that node, the longest path through it goes down the deepest left chain and the deepest right chain, so its length in edges is left height + right height, where each height is measured in nodes below this node.
So the diameter is the maximum of lh + rh over all nodes.
Brute Force
For every node, compute the height of its left and right subtree separately and take lh + rh. Keep the maximum. Recomputing heights for every node makes this O(n^2) on a skewed tree.
Optimal Approach: Update the Answer While Computing Height
Reuse the height function from the previous problem, and update a global diameter inside it.
- If the node is
null, return 0. - Compute
lhandrhrecursively. - Update
diameter = max(diameter, lh + rh). This is the longest path that turns at this node. - Return
1 + max(lh, rh)as the height for the parent.
Height returned to the parent is a single downward chain, while the diameter candidate uses both sides. Keeping those two ideas apart is the core of this problem.
Code
class Solution {int diameter = 0;int height(TreeNode* node) {if (node == nullptr) return 0;int lh = height(node->left);int rh = height(node->right);diameter = max(diameter, lh + rh);return 1 + max(lh, rh);}public:int diameterOfBinaryTree(TreeNode* root) {diameter = 0;height(root);return diameter;}};
Complexity
One pass computes the height and the diameter together. The brute force is O(n^2).
Recursion stack depth equals the tree height.