今天繼續二叉樹的遞歸套路。
一、判斷是否是滿二叉樹
滿二叉樹定義：對於高度為h的二叉樹，節點數為（2^h - 1）
1、遞歸套路思路
根據滿二叉樹的定義可以知道，我們每次只需要獲取高度、節點數即可。
也就是每次從左子樹和右子樹中我們都需要 高度、節點數 兩個數據，最後再根據高度和節點數的關係判斷是否是滿二叉樹。所以可以定義如下的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、寫代碼，在代碼中考慮如何把左樹的信息和右樹信息整合出整棵樹的信息
當看完了前幾篇的二叉樹遞歸套路，再看這個總結，是不是信手拈來。
