104 Maximum Depth of Binary Tree
104. Maximum Depth of Binary Tree
1. Question
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.
2. Implementation
(1) DFS
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
(2) BFS
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int size = 0, depth = 0;
while (!queue.isEmpty()) {
size = queue.size();
++depth;
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.remove();
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}
}
return depth;
}
}
3. Time & Space Complexity
DFS: 时间复杂度:O(n), 空间复杂度O(h)
BFS: 时间复杂度:O(n), 空间复杂度O(w), w为一层中有最多node的个数
Last updated
Was this helpful?