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.
1public class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 public int maxDepth(TreeNode root) {
10 if (root == null) return 0;
11 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
12 }
13}In Java, this function handles null root nodes by returning 0, indicative of no depth. It employs Math.max to evaluate the maximum depth recursively for the left and right subtrees.
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.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9def maxDepth(root: TreeNode) -> int:
10 if not root:
11 return 0
12 q = deque([root])
13 depth = 0
14 while q:
15 levelSize = len(q)
16 for _ in range(levelSize):
17 node = q.popleft()
18 if node.left:
19 q.append(node.left)
20 if node.right:
21 q.append(node.right)
22 depth += 1
23 return depthUsing Python's collections.deque for efficient pops from a queue's left side, each level’s nodes are tracked and processed, incrementing depth post each level traverse.