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

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

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

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