二叉树递归套路（3）（判断是否是满二叉树、最大子搜索二叉树的节点数）二叉树递归套路（3）：判断是

今天继续二叉树的递归套路。
一、判断是否是满二叉树满二叉树定义：对于高度为h的二叉树，节点数为（2^h - 1）
1、递归套路思路根据满二叉树的定义可以知道，我们每次只需要获取高度、节点数即可。
【二叉树递归套路（3）（判断是否是满二叉树、最大子搜索二叉树的节点数）】也就是每次从左子树和右子树中我们都需要高度、节点数两个数据，最后再根据高度和节点数的关系判断是否是满二叉树。所以可以定义如下的Info类

/** * @author Java和算法学习：周一 */ public static class Info { public int height; public int nodes; public Info(int height, int nodes) { this.height = height; this.nodes = nodes; } }

2、递归套路代码（1）首先判断为空时好不好设置，此时是好设置的，节点为空时new Info(0, 0)，即认为空节点高度为0、节点数为0。
（2）然后根据列出的所有可能性，编写递归套路的代码，因为要整个形成递归，所以每一步都要返回Info类。（无脑拿到左右子树的Info、拼凑自己的Info、返回自己的Info）

/** * @author Java和算法学习：周一 */ public static Info process(Node x) { if (x == null) { return new Info(0, 0); }// 获取左右子树的信息 Info leftInfo = process(x.left); Info rightInfo = process(x.right); // 拼凑自己的信息 int height = Math.max(leftInfo.height, rightInfo.height) + 1; int nodes = leftInfo.nodes + rightInfo.nodes + 1; return new Info(height, nodes); }

（3）主函数调用递归方法获取结果

/** * @author Java和算法学习：周一 */ public static boolean isFull(Node head) { if (head == null) { return true; } Info process = process(head); return (1 << process.height) - 1 == process.nodes; }

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/IsFullBinaryTree.java
二、求二叉树中最大子搜索二叉树的节点数给定一个二叉树，整体可能是、也可能不是搜索二叉树，但是它的某几个子树是搜索二叉树，要找到节点数最多的子搜索二叉树的节点数。
1、递归套路思路求最大子搜索二叉树，分为两种可能性，包含二叉树头节点，不包含二叉树头节点。
（1）不包含头节点：需要求左树的最大搜索二叉树的节点数，需要求右树的最大搜索二叉树的节点数
（2）包含头节点：需要判断左树是不是搜索二叉树，右树是不是搜索二叉树，左树的最大值是否小于头节点，右树的最小值是否大于头节点，同时还需要左树和右树的节点数。
也就是每次从左树和右树中我们都需要最大搜索二叉树的节点数、是否搜索二叉树、max、min、节点数，但是还能化简，如果最大搜索二叉树的节点数和节点数相等就意味着整个子树是搜索二叉树，所以可以化简为最大搜索二叉树的节点数、max、min、节点数。尽管我们最后只返回节点数，但是我们需要是否搜索二叉树、max、min来辅助求解节点数。最后，可以定义如下的Info类

/** * @author Java和算法学习：周一 */ public static class Info { // 最大满足搜索二叉树条件的子树大小 public int maxSubSize; public int max; public int min; // 整个子树的节点数 public int allSize; public Info(int maxSubSize, int max, int min, int allSize) { this.maxSubSize = maxSubSize; this.max = max; this.min = min; this.allSize = allSize; } }

2、递归套路代码（1）首先判断为空时好不好设置，此时是不好设置的，节点为空时max和min不好指定，所以节点为空时直接返回null，后面递归时再处理这个null即可。
（2）然后根据列出的所有可能性，编写递归套路的代码，因为要整个形成递归，所以每一步都要返回Info类。（无脑拿到左右子树的Info、拼凑自己的Info、返回自己的Info）

/** * @author Java和算法学习：周一 */ public static Info process(Node x) { if (x == null) { return null; }// 获取左右子树信息 Info leftInfo = process(x.left); Info rightInfo = process(x.right); // 拼凑自己的信息 int max = x.value; int min = x.value; int allSize = 1; if (leftInfo != null) { max = Math.max(leftInfo.max, max); min = Math.min(leftInfo.min, min); allSize += leftInfo.allSize; } if ((rightInfo != null)) { max = Math.max(rightInfo.max, max); min = Math.min(rightInfo.min, min); allSize += rightInfo.allSize; }// 左树最大搜索二叉树大小 int p1 = -1; if (leftInfo != null) { p1 = leftInfo.maxSubSize; }// 右树最大搜索二叉树大小 int p2 = -1; if (rightInfo != null) { p2 = rightInfo.maxSubSize; }// 最大子树包含头节点 int p3 = -1; // 左树是否是搜索二叉树 boolean leftSearch = leftInfo == null || leftInfo.maxSubSize == leftInfo.allSize; // 右树是否是搜索二叉树 boolean rightSearch = rightInfo == null || rightInfo.maxSubSize == rightInfo.allSize; if (leftSearch && rightSearch) { // 左树最大值是否比当前节点值小（空也认为比当前节点小） boolean lessMaxLessX = leftInfo == null || leftInfo.max < x.value; // 右树最小值是否比当前节点值大（空也认为比当前节点大） boolean rightMinMoreX = rightInfo == null || rightInfo.min > x.value; // 都满足，才能修改p3的值 if (lessMaxLessX && rightMinMoreX) { int leftSize = leftInfo == null ? 0 : leftInfo.allSize; int rightSize = rightInfo == null ? 0 : rightInfo.allSize; p3 = leftSize + rightSize + 1; } }// 最后修改，当前子树最大搜索二叉子树的大小 int maxSubSize = Math.max(p1, Math.max(p2, p3)); return new Info(maxSubSize, max, min, allSize); }

（3）主函数调用递归方法获取结果

/** * @author Java和算法学习：周一 */ public static int maxSubSearchBinaryTreeSize(Node head) { if (head == null) { return 0; } return process(head).maxSubSize; }

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/MaxSubSearchBinaryTreeSize.java
三、二叉树递归套路总结是不是觉得对二叉树的递归套路有点感觉了，是时候总结一下二叉树的递归套路了。
1、假设以X节点为头，假设可以向X左树和X右树要任何信息
2、在上一步的假设下，讨论以X为头节点的树，列出得到答案的可能性(最重要)
3、列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4、把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息Info
5、递归函数都返回Info，每一棵子树都这么要求
6、写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
当看完了前几篇的二叉树递归套路，再看这个总结，是不是信手拈来。