Problem
Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output
3 Solution
This solution uses Depth-First Search (DFS) with recursion. For each node, the maximum depth is calculated by finding the greater depth between its left and right subtrees.The current node contributes 1 to the depth, so we add 1 to the maximum depth returned by its children.
When a
null node is reached, its depth is 0. The recursion continues until the maximum depth of the entire tree is calculated.
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}
Complexity
Each node in the binary tree is visited exactly once, resulting in a time complexity ofO(n).
The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree. In the worst case of a completely skewed tree, this becomes O(n).