背景:
对某个二叉树,我们除了用肉眼可以看出其深度,还可以用算法来计算出它的深度。比如,下面的二叉树,一共有三层,它的深度就是3。如果某个分支的叶子结点没有左右子节点,就是它深度中较小的一个。
leetcode中,有一题求最小深度,如下图,最小深度为2。
package BinaryTree;
import java.util.Deque;
import java.util.LinkedList;
/**
* Demo class
*
* @author
* @date 2022/7/31
*/
public class MinDeep {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
//BFS是齐头并进式的遍历,它通过队列,把同一行的node全部add进去,然后计算层数。
public static int minDepth(TreeNode root) {
//对root判空
if (root == null) {
return 0;
}
//实例化队列,放入root,定义深度
Deque<TreeNode> deque = new LinkedList<TreeNode>();
deque.add(root);
int depth = 1;
//只要队列不为空,就一直处理
while (!deque.isEmpty()) {
int size = deque.size();
//对队列里的node逐个处理
for (int i = 0; i < size; i++) {
TreeNode cur = deque.pop();
//边界条件,某个node的左右子节点均为空
if (cur.left == null && cur.right == null) {
return depth;
}
if (cur.left != null) {
deque.add(cur.left);
}
if (cur.right != null) {
deque.add(cur.right);
}
}
depth++;
}
return depth;
}
public static void main(String[] args) {
// 0
// / \
// 1 2
// /
// 3
// /
// 4
TreeNode tree = new TreeNode();
tree.val = 0;
tree.left = new TreeNode();
tree.left.val = 1;
tree.right = new TreeNode();
tree.right.val = 2;
tree.left.left = new TreeNode();
tree.left.left.val = 3;
tree.left.left.left = new TreeNode();
tree.left.left.left.val = 4;
System.out.println(minDepth(tree));
}
}
拓展:如果需要求二叉树的最大深度,还是用BFS,只需要将上面的边界条件去掉即可。