二叉树递归套路：判断二叉树是否是完全二叉树、判断二叉树是否是平衡二叉树

二叉树递归套路：判断二叉树是否是完全二叉树、判断二叉树是否是平衡二叉树

文章目录

• 一、判断二叉树是否是完全二叉树
• • 1、经典写法思路
  • 2、递归套路思路
  • 3、递归套路代码
• 二、判断二叉树是否是平衡二叉树
• • 1、递归套路思路
  • 2、递归套路代码

二叉树的基本套路我们已经很熟悉了，接下来我们聊聊二叉树的递归套路，可以解决面试中绝大多数的二叉树问题，尤其是树型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信息

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）主函数调用递归方法获取结果

public static boolean isCompleteBinaryTree2(Node head) {
    if (head == null) {
        return true;
    }
    return process(head).isComplete;
}

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/IsCompleteBinaryTree.java

二、判断二叉树是否是平衡二叉树

平衡二叉树定义：二叉树每个子树中，左树最大高度和右树最大高度差小于等于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）

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）主函数调用递归方法获取结果

public static boolean isBalancedBinaryTree(Node head) {
    if (head == null) {
        return true;
    }
    return process(head).isBalanced;
}

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/IsBalancedBinaryTree.java

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