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

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