This approach involves using a recursive function that traverses the tree in a depth-first manner. For each node, calculate the maximum depth of its left and right subtrees, and add 1 for the current node itself. The function returns the maximum of these two values. This provides an elegant and intuitive solution, leveraging the inherent recursive structure of trees.
Time Complexity: O(n) where n is the number of nodes, as each node is visited once.
Space Complexity: O(h) where h is the height of the tree, due to the stack space in recursion.
1#include <algorithm>
2struct TreeNode {
3 int val;
4 TreeNode *left;
5 TreeNode *right;
6 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
7};
8
9int maxDepth(TreeNode* root) {
10 if (!root) return 0;
11 return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
12}This C++ solution also uses recursion. The std::max function is used to determine the larger depth between the left and right subtrees. The recursive nature mirrors the tree's structure.
This approach involves using a queue to perform a Breadth-First Search (BFS) on the tree. By iterating level by level, we increment the depth counter with each level traversed completely.
Time Complexity: O(n) due to each node being visited once.
Space Complexity: O(n) where n is the maximum number of nodes at any level.
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8 TreeNode(int x) { val = x; }
9}
10
11class Solution {
12 public int maxDepth(TreeNode root) {
13 if (root == null) return 0;
14 Queue<TreeNode> q = new LinkedList<>();
15 q.offer(root);
16 int depth = 0;
17 while (!q.isEmpty()) {
18 int levelSize = q.size();
19 for (int i = 0; i < levelSize; i++) {
20 TreeNode node = q.poll();
21 if (node.left != null) q.offer(node.left);
22 if (node.right != null) q.offer(node.right);
23 }
24 depth++;
25 }
26 return depth;
27 }
28}This Java solution uses a Queue to explore levels of the tree node by node. offer() inserts children nodes for subsequent processing, while poll() removes nodes, level by level incrementing depth.