Maximum Depth of Binary Tree
- 1 min read
- LC-Easy
- Binary Tree
3 years ago
Solution (Recursive DFS)
| Time | Space | Explanation |
|---|---|---|
O(n) | O(h) |
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root:
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
return 0
Solution (Iterative Stack-based)
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
max_depth = 0
stack = [(root, 1)]
while stack:
node, depth = stack.pop()
max_depth = max(depth, max_depth)
if node.left:
stack.append((node.left, depth + 1))
if node.right:
stack.append((node.right, depth + 1))
return max_depth