25_111. 二叉树的最小深度
题目描述：
解题思路：
- 深度优先搜索：这个要注意返回条件
- 当
root == null时，返回0；root.left == null && root.right == null，返回1root.left == null || root.right == null,返回不为空的那个深度else返回左右子树的最小值 + 1- 广度优先搜索：对于这种层次遍历，第一次发现
node.left == null && node.right == null时，返回深度即可，注意要为每一层维护一个深度的变量，可以通过for (int i = 0; i < queue.size(), i++)来实现，也可以通过构造一个类，类中维护着各个节点的深度消息来实现。
代码：
深度优先
//深度优先
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null || root.right == null) {
return leftDepth + rightDepth + 1;
}
return Math.min(leftDepth, rightDepth) + 1;
}
广度优先
//广度优先
class Solution {
public int minDepth(TreeNode root) {
Queue queue = new LinkedList<>();
if (root == null) {
return 0;
}
int depth = 0;
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return depth;
}
}