• 欢迎光临~

# 代码随想录训练营｜Day 16｜104，111，222

### 104. Maximum Depth of Binary Tree

Given the `root` of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

``````Input: root = [3,9,20,null,null,15,7]
Output: 3
``````

Example 2:

``````Input: root = [1,null,2]
Output: 2
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `100 <= Node.val <= 100`

Recursion

``````class solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
``````

Iteration

``````class solution {
/**
* 迭代法，使用层序遍历
*/
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = deque.poll();
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
}
return depth;
}
}
``````

Time Complexity：O(n)
Space Complexity：O(log n)

For Future References

### 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

``````Input: root = [3,9,20,null,null,15,7]
Output: 2
``````

Example 2:

``````Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 105]`.
• `1000 <= Node.val <= 1000`

• 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
• 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
• 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

Recursion

``````class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
// 左右结点都不为null
return Math.min(leftDepth, rightDepth) + 1;
}
}
``````

Iteration

``````class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode poll = deque.poll();
if (poll.left == null && poll.right == null) {
// 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
return depth;
}
if (poll.left != null) {
deque.offer(poll.left);
}
if (poll.right != null) {
deque.offer(poll.right);
}
}
}
return depth;
}
}
``````

Time Complexity：O(n)
Space Complexity：O(log n)

For Future References

### 222. Count Complete Tree Nodes

Given the `root` of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between `1` and `2h` nodes inclusive at the last level `h`.

Design an algorithm that runs in less than `O(n)` time complexity.

Example 1:

``````Input: root = [1,2,3,4,5,6]
Output: 6
``````

Example 2:

``````Input: root = []
Output: 0
``````

Example 3:

``````Input: root = [1]
Output: 1
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 5 * 104]`.
• `0 <= Node.val <= 5 * 104`
• The tree is guaranteed to be complete.

``````class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (leftDepth == rightDepth) {// 左子树是满二叉树
// 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点
return (1 << leftDepth) + countNodes(root.right);
} else {// 右子树是满二叉树
return (1 << rightDepth) + countNodes(root.left);
}
}

private int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
root = root.left;
depth++;
}
return depth;
}
}
``````

Time Complexity：O(log n × log n)
Space Complexity：O(log n)

For Future References