二叉树递归套路（2）（判断二叉树是否是搜索二叉树、二叉树的最大距离）二叉树递归套路（2）：判断二

本篇继续来聊聊二叉树的递归套路。
一、判断二叉树是否是搜索二叉树搜索二叉树定义：二叉树中的任意一个以X为头的子树，左子树都比X小，右子树都比X大。（经典的搜索二叉树是没有重复值的）
1、经典做法 【二叉树递归套路（2）（判断二叉树是否是搜索二叉树、二叉树的最大距离）】中序遍历，结果是递增的，说明这是搜索二叉树。
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）主函数调用递归方法获取结果