Question
Formatted question description: https://leetcode.ca/all/104.html
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.
@tag-tree
Algorithm
BFS
The layer sequence traverses the binary tree, and then counts the total number of layers, which is the maximum depth of the binary tree. Note that the for loop in the while loop has a trick.
You must put q.size() in the initialization, not in the judgment stop In the condition, because the size of q changes at any time, an error will occur in the stop condition.
DFS
Typical DFS.
Code
Java
import java.util.LinkedList;
import java.util.Queue;
public class Maximum_Depth_of_Binary_Tree {
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// bfs
public class Solution_countAsMarker {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int currentLevelCount = 1;
int nextLevelCount = 0;
int depth = 0;
while (!q.isEmpty()) {
TreeNode current = q.poll();
currentLevelCount--;
if (current.left != null) {
q.offer(current.left);
nextLevelCount++;
}
if (current.right != null) {
q.offer(current.right);
nextLevelCount++;
}
if (currentLevelCount == 0) {
currentLevelCount = nextLevelCount;
nextLevelCount = 0;
depth++;
}
}
return depth;
}
}
// @note: just a bfs, counting total level
public class Solution_iteration_nullAsMarker {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
q.offer(null);// @note: use null as marker for end of level
int depth = 0;
while (!q.isEmpty()) {
TreeNode current = q.poll();
if (current == null) {
depth++;
if (!q.isEmpty()) {
q.offer(null);
}
continue;
}
if (current.left != null) {
q.offer(current.left);
}
if (current.right != null) {
q.offer(current.right);
}
}
return depth;
}
}
public class Solution_recursion {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
}