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

二叉树的基本套路我们已经很熟悉了，接下来我们聊聊二叉树的递归套路，可以解决面试中绝大多数的二叉树问题，尤其是树型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...
【二叉树递归套路（判断二叉树是否是完全二叉树、判断二叉树是否是平衡二叉树）】是不是发现用递归套路来解瞬间难度降低了许多，别急，二叉树的递归套路远不止这点，这才套路入门呢，后面还有好几篇介绍递归套路技巧的。