Maximum Depth of Binary Tree
Depth is 1 + max(left depth, right depth); the empty tree has depth 0.
2 min read
tree dfs
Problem#
Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from root to a leaf.
Examples#
[3,9,20,null,null,15,7]→3[1,null,2]→2
Constraints#
- The number of nodes is in
[0, 10^4].
Approach#
Recursion. maxDepth(null) = 0; otherwise 1 + max(maxDepth(left), maxDepth(right)).
Solution#
class Solution {public: int maxDepth(TreeNode* root) { if (!root) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); }};func maxDepth(root *TreeNode) int { if root == nil { return 0 } l := maxDepth(root.Left) r := maxDepth(root.Right) if l > r { return 1 + l } return 1 + r}from typing import Optional
class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))function maxDepth(root) { if (!root) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }}function maxDepth(root: TreeNode | null): number { if (!root) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}Editorial#
The empty subtree is the base case (depth 0). Every recursive call adds one for the current node and takes the deeper of its two children.
Complexity#
- Time: O(n).
- Space: O(h).
Concept revision#
Related#