本篇繼續來聊聊二叉樹的遞歸套路。
一、判斷二叉樹是否是搜索二叉樹
搜索二叉樹定義：二叉樹中的任意一個以X為頭的子樹，左子樹都比X小，右子樹都比X大。（經典的搜索二叉樹是沒有重複值的）
1、經典做法
中序遍歷，結果是遞增的，説明這是搜索二叉樹。
2、遞歸套路思路
分析任意一個以X為頭的子樹，滿足以X為頭的子樹是搜索二叉樹的條件（列出所有可能性）
1）左子樹是搜索二叉樹
2）右子樹是搜索二叉樹
3）左子樹的最大值 小於 X
4）右子樹的最小值 大於 X
滿足這四個條件才能説以X為頭的子樹是平衡二叉樹。
問題來了：此時發現我需要從左子樹和右子樹中獲取的結果不一致（一個是要最小值、一個是要最大值），不好拼湊出遞歸。咋辦？好説，我們直接求全集（小孩子才做選擇，成年人不做選擇，都要），左子樹我們求最大值和最小值，右子樹也是。
也就是每次從左子樹和右子樹中我們都需要 是否搜索二叉樹、最大值、最小值 三個數據，儘管我們最後只返回是否搜索二叉樹，但是我們需要最大值和最小值來輔助我們判斷是否搜索，所以可以定義如下的Info類
/**
* @author Java和算法學習：週一
*/
public static class Info {
public boolean isSearch;
public int max;
public int min;
public Info(boolean isSearch, int max, int min) {
this.isSearch = isSearch;
this.max = max;
this.min = min;
}
}
3、遞歸套路代碼
（1）首先判斷為空時好不好設置，此時不好設置，節點為空時max和min不好指定，所以節點為空時直接返回null，後面遞歸時再處理這個null即可。
（2）然後根據列出的所有可能性，編寫遞歸套路的代碼，因為要整個形成遞歸，所以每一步都要返回Info類。（無腦拿到左右子樹的Info、拼湊自己的Info、返回自己的Info）
/**
* 判斷是否是搜索二叉樹的遞歸套路寫法
*
* @author Java和算法學習：週一
*/
public static Info process(Node x) {
// 為空時，max和min無法賦值，所以此處返回null
if (x == null) {
return null;
}
// 獲取左右子樹的數據
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// 拼湊自己的數據
boolean isSearch = true;
// 當前節點不是搜索二叉樹的情況
// 1.左子樹不是搜索二叉樹
// 2.右子樹不是搜索二叉樹
// 3.左子樹最大值大於當前節點
// 4.右子樹最小值小於當前節點
if (leftInfo != null && (!leftInfo.isSearch || leftInfo.max >= x.value)) {
isSearch = false;
}
if (rightInfo != null && (!rightInfo.isSearch || rightInfo.min <= x.value)) {
isSearch = false;
}
int max = x.value;
int min = x.value;
if (leftInfo != null) {
max = Math.max(leftInfo.max, max);
min = Math.min(leftInfo.min, min);
}
if (rightInfo != null) {
max = Math.max(rightInfo.max, max);
min = Math.min(rightInfo.min, min);
}
return new Info(isSearch, max, min);
}
（3）主函數調用遞歸方法獲取結果
/**
* @author Java和算法學習：週一
*/
public static boolean isSearchBinaryTree(Node head) {
if (head == null) {
return true;
}
return process(head).isSearch;
}
所有代碼地址：
https://github.com/monday-pro...
二、二叉樹的最大距離
給定一個二叉樹，任何兩個節點之間都存在距離，返回整個二叉樹的最大距離。兩個節點的距離表示從一個節點到另一個節點最短路徑上的節點數（包含兩個節點自己）
1、遞歸套路思路
首先分析以X為頭的二叉樹，它的最大距離的可能性有兩類，不經過X、經過X。
不經過X：需要獲取左子樹和右子樹各自的最大距離
經過X：（左樹高度 + 右樹高度 + 1）即是最大距離
也就是每次從左子樹和右子樹中我們都需要 最大距離、高度 兩個數據，最後再取 左子樹最大距離、右子樹最大距離、（左樹高度 + 右樹高度 + 1） 的最大值即是整個樹的最大距離。儘管我們最後只返回最大距離，但是我們需要高度來輔助我們計算最大距離，所以可以定義如下的Info類
/**
* @author Java和算法學習：週一
*/
public static class Info {
public int height;
public int maxDistance;
public Info(int height, int maxDistance) {
this.height = height;
this.maxDistance = maxDistance;
}
}
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);
// 拼湊處理自己的信息
// 最大高度是 左右子樹最大高度 + 1
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// 最大距離是 左子樹最大距離、右子樹最大距離、（左樹高度 + 右樹高度 + 1） 三個的最大值
int maxDistance = Math.max((leftInfo.height + rightInfo.height + 1),
Math.max(leftInfo.maxDistance, rightInfo.maxDistance));
return new Info(height, maxDistance);
}
（3）主函數調用遞歸方法獲取結果
/**
* @author Java和算法學習：週一
*/
public static int maxDistance(Node head) {
if (head == null) {
return 0;
}
return process(head).maxDistance;
}
所有代碼地址：
https://github.com/monday-pro...
這是二叉樹遞歸套路解法的第二篇，結合上一篇是不是發現又有了新的收穫呢。這次我們又學會了左右子樹需要獲取的值不同時如何處理、在節點為空時不好設置值時如何處理等。
