共计 3725 个字符，预计需要花费 10 分钟才能阅读完成。
二叉树的根本套路咱们曾经很相熟了，接下来咱们聊聊二叉树的递归套路， 能够解决面试中绝大多数的二叉树问题，尤其是树型 dp 问题，其本质是利用递归遍历二叉树的便利性 。
判断二叉树是否是齐全二叉树
1、经典写法思路
（1）某个节点有右孩子无左孩子，则肯定不是齐全二叉树
（2）当第一次遇到左右孩子不双全的节点时，当前遇到的节点都是叶节点
2、递归套路思路
对于任意一颗子树，判断是否是齐全二叉树的条件（ 列出所有可能性 ）
（1）左树是满的，右树是满的，左树高度 = 右树高度
（2）左树是齐全二叉树，右树是满的，左树高度 = 右树高度 + 1
（3）左树是满的，右树是满的，左树高度 = 右树高度 + 1
（4）左树是满的，右树是齐全二叉树，左树高度 = 右树高度
只有这 4 种状况二叉树才可能是齐全二叉树（当然也可能是满二叉树，满二叉树自身也是齐全二叉树）
也就是每次从左子树和右子树中咱们都须要 是否满二叉树、是否齐全二叉树、高度 三个数据，只管咱们最初只返回是否齐全二叉树，然而咱们须要高度、是否满来辅助咱们判断是否齐全二叉树，所以能够定义如下的 Info 类
public static class Info {
public boolean isFull;
public boolean isComplete;
public int height;
public Info(boolean isFull, boolean isComplete, int height) {
this.isFull = isFull;
this.isComplete = isComplete;
this.height = height;
}
}
3、递归套路代码
（1）首先判断为空时好不好设置，此时是好设置的， 节点为空时 new Info(true, true, 0)，即认为空节点是满二叉树、是齐全二叉树、高度为 0。
（2）而后依据列出的所有可能性，编写递归套路的代码，因为要整个造成递归，所以每一步都要返回 Info 类，不然咋递归上来呢？
此步的外围套路就以下三步：
1）无脑获取左右子树的 Info 信息
2）依据左右子树拼凑本人的 Info 信息
3）返回本人的 Info 信息
/**
* @author Java 和算法学习：周一
*/
public static Info process(Node x) {if (x == null) {return new Info(true, true, 0);
}
// 获取左右子树
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// 拼凑本人的信息
boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
boolean isComplete = false;
if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
// 左满，右满，高度相等
isComplete = true;
} else if (leftInfo.isComplete && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
// 左齐全，右满，高度差 1
isComplete = true;
} else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
// 左满、右满，高度差为 1
isComplete = true;
} else if (leftInfo.isFull && rightInfo.isComplete && leftInfo.height == rightInfo.height) {
// 左满、右齐全，高度相等
isComplete = true;
}
// 左右子树高度最大的加上本人的高度 1，即是此节点的高度
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
return new Info(isFull, isComplete, height);
}
（3）主函数调用递归办法获取后果
/**
* 递归套路解法
*
* @author Java 和算法学习：周一
*/
public static boolean isCompleteBinaryTree2(Node head) {if (head == null) {return true;}
return process(head).isComplete;
}
所有代码地址：
https://github.com/monday-pro…
判断二叉树是否是均衡二叉树
均衡二叉树定义：二叉树每个子树中，左树最大高度和右树最大高度差小于等于 1。
1、递归套路思路
剖析对于任意一个节点，满足以此节点为头的子树是均衡二叉树的条件（ 列出所有可能性 ）
（1）左树是均衡二叉树
（2）右树是均衡二叉树
（3）左树高度、右树高度 差值小于等于 1
满足这三个条件能力说以此节点为头的子树是均衡二叉树。
也就是每次从左子树和右子树中咱们都须要 是否均衡、高度 两个数据，只管咱们最初只返回是否均衡，然而咱们须要高度来辅助咱们判断是否均衡，所以能够定义如下的 Info 类
public static class Info{
public boolean isBalanced;
public int height;
public Info(boolean b, int h) {
this.isBalanced = b;
this.height = h;
}
}
2、递归套路代码
（1）首先判断为空时好不好设置，此时也是好设置的， 节点为空时 new Info(true, 0)，即认为空节点是均衡二叉树、高度为 0。
（2）而后依据列出的所有可能性，编写递归套路的代码，因为要整个造成递归，所以每一步都要返回 Info 类。（拿到左右子树的 Info、拼凑本人的 Info、返回本人的 Info）
/**
* 判断以某个节点为头的子树是否是均衡二叉树
*
* @author Java 和算法学习：周一
*/
public static Info process(Node x) {if (x == null) {return new Info(true, 0);
}
// 1. 拿到左右子树的信息
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// 2. 拼凑我本人的信息
// 默认是均衡的
boolean isBalanced = true;
// 哪些状况会造成不均衡：1. 左树不均衡 2. 右树不均衡 3. 左右子树的高度差大于 1
if (!leftInfo.isBalanced || !rightInfo.isBalanced || Math.abs(leftInfo.height - rightInfo.height) > 1) {isBalanced = false;}
// 左右子树中最大高度，加上到本人的高度
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// 3. 返回本人的信息
return new Info(isBalanced, height);
}
（3）主函数调用递归办法获取后果
/**
* @author Java 和算法学习：周一
*/
public static boolean isBalancedBinaryTree(Node head) {if (head == null) {return true;}
return process(head).isBalanced;
}
所有代码地址：
https://github.com/monday-pro…
是不是发现用递归套路来解霎时难度升高了许多，别急，二叉树的递归套路远不止这点，这才套路入门呢，前面还有好几篇介绍递归套路技巧的 。