本篇持续来聊聊二叉树的递归套路。

一、判断二叉树是否是搜寻二叉树

搜寻二叉树定义：二叉树中的任意一个以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...

这是二叉树递归套路解法的第二篇，联合上一篇是不是发现又有了新的播种呢。这次咱们又学会了左右子树须要获取的值不同时如何解决、在节点为空时不好设置值时如何解决等。