# 104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
# Solution
Approach 1: Recursion.
Approach 2: Iteration.
# Code (Python)
Approach 1:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# recursive -- DFS
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
Approach 2:
def maxDepth(self, root):
# iterative -- BFS
if not root:
return 0
level = [root]
depth = 0
while level:
depth += 1
next_level = []
for node in level:
for child in (node.left, node.right):
if child:
next_level.append(child)
level = next_level
return depth
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}
};
Approach 2:
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
stack<pair<TreeNode*, int>> nodeStack;
nodeStack.push(pair<TreeNode*, int>(root, 1));
int max = 0;
while (!nodeStack.empty())
{
TreeNode *node = nodeStack.top().first;
int depth = nodeStack.top().second;
nodeStack.pop();
if (depth > max) max = depth;
if (node->left != NULL)
nodeStack.push(pair<TreeNode*, int>(node->left, depth+1));
if (node->right != NULL)
nodeStack.push(pair<TreeNode*, int>(node->right, depth+1));
}
return max;
}
};