本篇持续来聊聊二叉树的递归套路。
一、判断二叉树是否是搜寻二叉树
搜寻二叉树定义：二叉树中的任意一个以 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…
这是二叉树递归套路解法的第二篇，联合上一篇是不是发现又有了新的播种呢。这次咱们又学会了左右子树须要获取的值不同时如何解决、在节点为空时不好设置值时如何解决等。