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 {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return maxDiameter;
}
public int dfs(TreeNode node) {
if (node == null) return 0;
int leftHeight = dfs(node.left);
int rightHeight = dfs(node.right);
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
return Math.max(leftHeight, rightHeight) + 1;
}
}Follow-up:
What if the tree is not binary?
