一、二叉树最大深度
二叉树的最大深度是根节点到叶子节点的最大长度
1.1 最大深度的递归实现
传入根节点，得到左右子树的高度，取较大值。然后不停的递归即可。这里需要注意的是如果不是空结点返回的是深度+1.
就比如一颗二叉树
1
2 3
传入根节点1，不为空
传入左孩子结点（左孩子结点的左右孩子均为空，则返回0）
传入右孩子结点（右孩子结点的左右孩子均为空，则返回0）
最终返回0
显然是不对的。因为子树的根节点即使没有左右孩子，高度也应该为1
下面是实现代码:
public static int maxDeepRecrusion(BTNode node) {
if (node == null) {
return 0;
}
int leftDeep = maxDeepRecrusion(node.leftChild);
int rightDeep = maxDeepRecrusion(node.rightChild);
//加1是因为要把每个字数的根节点也算进去
return leftDeep > rightDeep ? (leftDeep + 1) : (rightDeep + 1);
}
1.2 最大深度的非递归实现
前面我们介绍的最大宽度利用的是层次遍历的思路，得到了每一层的结点数量，在此基础上我们只需要每层+1即可得到最大深度
public static int maxDeep(BTNode node) {
//如果为空
if(node == null){
return 0;
}
int maxDeep = 0, width;
ArrayDeque<BTNode> queue = new ArrayDeque<>();
//根节点入队
queue.add(node);
while (!queue.isEmpty()) {
width = queue.size();
//每遍历一层深度+1
maxDeep += 1;
//注意这里循环的次数是width,出队的仅仅是每一层的元素
for (int i = 0; i < width; i++) {
BTNode nodeTemp = queue.poll();
if (nodeTemp.leftChild != null) {
queue.add(nodeTemp.leftChild);
}
if(nodeTemp.rightChild != null) {
queue.add(nodeTemp.rightChild);
}
}
}
return maxDeep;
}
二、二叉树的最小深度
二叉树的最小深度即为是根节点到叶子节点的最小长度
2.1 最小深度的递归实现
- 如果根节点为空，则最小深度为0
- 如果只有一个根节点(根节点的左右子树为空)，则最小深度为1
- 如果左子树为空，右子树不为空，最小深度为1+右子树的最小深度
- 如果右子树为空，左子树不为空，最小深度为1+左子树的最小深度
- 如果左右子树都不为空，则最小深度为1+左右子树最小深度中的较小值
我们由此可得代码：
public static int minDeepRecrusion(BTNode node) {
if(node == null) {
return 0;
}
if (node.leftChild == null) return minDeepRecrusion(node.rightChild) + 1;
if (node.rightChild == null) return minDeepRecrusion(node.leftChild) + 1;
return Math.min(minDeepRecrusion(node.leftChild),minDeepRecrusion(node.rightChild))+1;
}
其实之前的递归代码也可以省去变量，用这种Math.min()的方式。
当我们使用递归的方式求最小深度的时候要考虑到一种情况，如果根节点左孩子一个结点，右孩子深度为1000，那么递归方法仍然会去遍历1000次，所以从效率上来讲是很浪费资源的，下面介绍的非递归实现方式就不会出现这个问题
2.2 最小深度的非递归实现
非递归最小深度也是在层次遍历的基础上，上一步我们已经得到了最大深度的层次遍历，我们只需要在此基础上加上条件，当出现叶子结点的时候结束遍历，返回当前深度即可。
public static int minDeep(BTNode node) {
//如果为空
if(node == null){
return 0;
}
int minDeep = 0, width;
ArrayDeque<BTNode> queue = new ArrayDeque<>();
//根节点入队
queue.add(node);
while (!queue.isEmpty()) {
width = queue.size();
//若每一层的宽度大于maxWidth，则重新赋值
minDeep += 1;
//注意这里循环的次数是width,出队的仅仅是每一层的元素
for (int i = 0; i < width; i++) {
BTNode nodeTemp = queue.poll();
//左右均为空表明是叶子结点
if(nodeTemp.rightChild == null && nodeTemp.leftChild == null){
return minDeep;
}
if (nodeTemp.leftChild != null) {
queue.add(nodeTemp.leftChild);
}
if(nodeTemp.rightChild != null) {
queue.add(nodeTemp.rightChild);
}
}
}
return minDeep;
}
三、测试代码
/**
* 构建二叉树
* 3
* 2 4
* 5 2 2 4
* 5
* @param args
*/
public static void main(String[] args) {
int[] a = {3, 2, 4, 5, 2, 2, 4, 5};
//利用数组创建完全二叉树
BTNode root = BTNodeUtil.createBTNodebyArray(a);
System.out.println("二叉树的层次遍历为：");
level(root);
System.out.println();
System.out.println("该二叉树的递归最大深度为：" + maxDeepRecrusion(root));
System.out.println("该二叉树的非递归最大深度为：" + maxDeep(root));
System.out.println("该二叉树的递归最小深度为：" + minDeepRecrusion(root));
System.out.println("该二叉树的递归最小深度为：" + minDeep(root));
}
输出为
二叉树的层次遍历为：
3 2 4 5 2 2 4 5
该二叉树的递归最大深度为：4
该二叉树的非递归最大深度为：4
该二叉树的递归最小深度为：3
该二叉树的递归最小深度为：3
