提示：我的整个生命，只是一场为了提升社会地位的低俗斗争。--埃莱娜·费兰特《失踪的孩子》
这一关我们看一些比较特别的题目，关于二叉树的深度和高度问题。这些对递归的考察更高些，要注意了。
给你一个二叉树：
我们看下力扣的相关题目，这些是关于深度和高度的问题。
推荐题目⭐⭐⭐⭐：
参考题目介绍：104. 二叉树的最大深度 - 力扣（LeetCode）
首先最大深度：根节点到最远叶子节点的最长路径上的节点数。说明叶子节点是没有子节点的。
我们看看下面这些。（上图的最大深度为3）
对于node(3)，最大深度自然是左右子节点+1，左右子节点有可能为空，只要有一个，树的最大高度就是1 + 1 = 2。然后再增加几个节点：
很显然相对于node(20)，最大的深度自然是左右子节点+1，左右子节点有可能为空，只要右一个，树的最大高度就是1 + 1 = 2，用代码表示就是：
int depth = 1 + math(leftDepth,rightDepth);
对于3，则是左右子树深度最大的那个再加1，具体谁的更大，则不必管旭，所以对于node(3)的逻辑判断就是：
int leftDepth = getDepth(root.left); //左
int rightDepth = getDepth(root.right); // 右
int depth = 1 + math(leftDept,rightDept); // 中
那么什么时候结束呢？这里仍然是root == null 返回0就行了，至于入参，自然是要处理的子树的根节点root，而返回值则是当前root所在子树的最大高度，所以合在一起就是：
/**
* 通过递归计算二叉树的深度
*
* @param root
* @return
*/
public static int maxDepth_1(TreeNode root) {
if(root == null) {
return 0;
}
int leftDepth = maxDepth_1(root.left);
int rightDepth = maxDepth_1(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
上面代码先拿到左右子树的结果，再计算Math.max(left,right) + 1，本质上和后序遍历一样，一次者可以看做事后序遍历的扩展问题。
我们继续看这个题目，如果我们确定树最大有几层是不是也确定了最大深度呢？当然，另一个思路不就来了，我们直接套用层序遍历的代码：
具体细节注意一下：我们这里获取层数，每获取一层，就加一。
/**
* 通过层次遍历来求最大深度
*
* @param root
* @return
*/
public static int maxDepth_2(TreeNode root) {
// 校验参数
if (root == null){
return 0;
}
// 创建空间
int res = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
// 根节点入队，不断的遍历根节点
queue.offer(root);
while(!queue.isEmpty()){
// 获取到每层多少个
int size = queue.size();
// size == 0 说明这一层遍历完了
while(size > 0){
// 遍历
TreeNode node = queue.poll();
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
size--;
}
res++;
}
return res;
}
参考题目介绍：110. 平衡二叉树 - 力扣（LeetCode）
补充一个知识点：高度和深度怎么区分?
关于根节点的深度是1还是0的问题，不同的地方标准不一样，力扣的题目中都是以根节点的深度为1，其他的我们先不管。
我们接着看一下这个问题：
很显然只要有两次的时候一定是平衡的，因为对于node(3)，左右孩子如果只有一个，呢么高度差就是1；如果左右孩子都没有或者都有，则高度差为0。但是如果再加一层呢？
看下图：
对于node(3)，需要同时知道自己左右子树的最大高度差是否< 2.
也是就是说：
int left = recur(root.left);
int right = recur(root.right);
return Math.abs(left - right) < 2 ? Math.max(left,right) + 1:-1;
我们此时已经写出了核心代码，假设子树已经不平衡了，我们就不需要再递归下去而是直接返回就行了。例如这个树中的节点20：
综合考虑几种情况，我们看下完整的代码：
/**
* 方法1 自下而上
*
* @param root
* @return
*/
public static boolean isBalanced_1(TreeNode root) {
return recur(root) == -1;
}
public static int recur(TreeNode root) {
if (root == null){
return 0;
}
int left = recur(root.left);
if (left == -1){
return -1;
}
int right = recur(root.right);
if (right == -1){
return -1;
}
return Math.abs(left - right) < 2 ? Math.max(left,right) + 1: -1;
}
/**
* 2.自上而下
*
* @param root
* @return
*/
public static boolean isBalanced_2(TreeNode root) {
if (root == null){
return true;
}
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced_2(root.left) && isBalanced_2(root.right);
}
public static int depth(TreeNode root){
if (root == null){
return 0;
}
return Math.max(depth(root.left),depth(root.right)) + 1;
}
参考题目介绍：111. 二叉树的最小深度 - 力扣（LeetCode）
既然有最大深度，可能会有最小深度？这不他就来了，怎么找出最小深度呢？
最小深度：从根节点到最接近叶子节点的最短路径上的节点数量。
看下下面这个特殊例子： 答案是 2 【说明】：叶子节点是指没有子节点的节点。
前面两道题涉及到最大深度，这里讲max改成min是不是就可以解决了呢？ 不行，你注意看上图：
这里的关键问题是题目中说的：最小深度是从根节点到最近叶子节点的最短路径上的节点数量，也就是说最小深度的一层必须要有叶子节点，不能直接使用。
这里的核心问题仍然是终止条件分析：
最后如果左右子树都不空，返回左右子树深度最小值+1。
我们看下代码展示