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 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public int MaxDepth(TreeNode root) {
10 if (root == null) return 0;
11 return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
12 }
13}C# uses a similar pattern to other languages: check for null, invoke recursion, and apply the Math.Max function across child nodes to determine depth.
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.