Maximum Depth of Binary Tree
Tree, BFS, DFS
Easy
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],
1
3
2
/ \
3
9 20
4
/ \
5
15 7
Copied!
return its depth = 3.

Solution

*Recursive

1
public int maxDepth(TreeNode root) {
2
if(root==null){
3
return 0;
4
}
5
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
6
}
Copied!

DFS

1
public int maxDepth(TreeNode root) {
2
if(root == null) {
3
return 0;
4
}
5
6
Stack<TreeNode> stack = new Stack<>();
7
Stack<Integer> value = new Stack<>();
8
stack.push(root);
9
value.push(1);
10
int max = 0;
11
while(!stack.isEmpty()) {
12
TreeNode node = stack.pop();
13
int temp = value.pop();
14
max = Math.max(temp, max);
15
if(node.left != null) {
16
stack.push(node.left);
17
value.push(temp+1);
18
}
19
if(node.right != null) {
20
stack.push(node.right);
21
value.push(temp+1);
22
}
23
}
24
return max;
25
}
Copied!

*BFS

1
public int maxDepth(TreeNode root) {
2
if(root == null) {
3
return 0;
4
}
5
Queue<TreeNode> queue = new LinkedList<>();
6
queue.offer(root);
7
int count = 0;
8
while(!queue.isEmpty()) {
9
int size = queue.size();
10
while(size-- > 0) {
11
TreeNode node = queue.poll();
12
if(node.left != null) {
13
queue.offer(node.left);
14
}
15
if(node.right != null) {
16
queue.offer(node.right);
17
}
18
}
19
count++;
20
}
21
return count;
22
}
Copied!
Last modified 1yr ago
Copy link