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