Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth. A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Constraints:
- The number of nodes in the tree is in the range [0, 10^4].
- (-100 <= Node.val <= 100)
Examples:
Input: [3,9,20,null,null,15,7]
Output: 3
Explanation: The maximum depth of the binary tree is 3.
Solutions
Recursive Depth-First Search
Time: O(n)Space: O(h)
This solution uses a recursive depth-first search approach to calculate the maximum depth of the binary tree. It checks if the root is null, and if so, returns 0. Otherwise, it recursively calculates the maximum depth of the left and right subtrees and returns the maximum of the two plus 1.
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
}
;Follow-up:
What if the tree is not a binary tree, but a k-ary tree?
