二叉树的根本套路咱们曾经很相熟了，接下来咱们聊聊二叉树的递归套路，能够解决面试中绝大多数的二叉树问题，尤其是树型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...

是不是发现用递归套路来解霎时难度升高了许多，别急，二叉树的递归套路远不止这点，这才套路入门呢，前面还有好几篇介绍递归套路技巧的。