Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to a leaf.
Constraints:
- The number of nodes is in the range
[0, 10^4]. -100 <= Node.val <= 100
Intuition
1 12 / \3 2 34 / \ \5 4 5 6The depth of this tree is 3. Think of it recursively: the depth of a tree is one (for the root) plus the deeper of its two subtrees. An empty tree has depth 0, which is the base case.
This is a postorder idea: you need the answers from both children before you can answer for the parent.
Approach: Recursion
- If the node is
null, return 0. - Ask the left subtree for its depth,
lh. - Ask the right subtree for its depth,
rh. - Return
1 + max(lh, rh).
A level-order (BFS) traversal also works: count how many levels the queue goes through. The recursive version is shorter and is the building block for the next few problems (balanced tree, diameter, max path sum).
Code
class Solution {public:int maxDepth(TreeNode* root) {if (root == nullptr) return 0;int lh = maxDepth(root->left);int rh = maxDepth(root->right);return 1 + max(lh, rh);}};
Complexity
Every node is visited exactly once.
The recursion stack goes as deep as the tree height: O(log n) when balanced, O(n) when skewed.