求二叉树中最大的二叉搜索子树的头节点
作者：Grey
原文地址：
题目描述#
给定一棵二叉树的头节点head， 返回这颗二叉树中最大的二叉搜索子树的头节点。
暴力解法#
定义递归函数
TreeNode maxSubBSTHead1(TreeNode head)
递归含义表示：以head为头的二叉树中最大的二叉搜索子树的头结点是什么。
接下来是 base case，
if (head == null) {
return null;
}
定义一个辅助函数getBSTSize(head)，这个函数表示：如果以head为头的树是二叉搜索树，则返回其大小，否则返回 0。
getBSTSize(head)的实现思路也比较简单，即通过中序遍历收集以 head 为头的树，如果这个树满足二叉搜索子树，则返回二叉搜索子树的大小，如果以 head 的头不是二叉搜索树，直接返回 0。
代码如下
public static int getBSTSize(TreeNode head) {
if (head == null) {
return 0;
}
ArrayList arr = new ArrayList<>();
// 中序遍历收集以 head 为头的二叉树，存在数组中
in(head, arr);
for (int i = 1; i < arr.size(); i++) {
if (arr.get(i).val <= arr.get(i - 1).val) {
return 0;
}
}
return arr.size();
}
实现了如上方法，主函数直接做如下调用即可，代码说明见注释：
public static TreeNode maxSubBSTHead1(TreeNode head) {
if (head == null) {
return null;
}
// 以 head 为头的二叉搜索子树大小不为0，说明head这就是最大的二叉搜索子树头！
if (getBSTSize(head) != 0) {
return head;
}
// 去左树上找哪个结点是最大二叉搜索子树的头结点
TreeNode leftAns = maxSubBSTHead1(head.left);
// 去右树上找哪个结点是最大二叉搜索子树的头结点
TreeNode rightAns = maxSubBSTHead1(head.right);
// 左右树哪个二叉搜索子树更大，就返回哪个结点
return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
}
二叉树的递归套路#
定义如下数据结构
public static class Info {
public TreeNode maxSubBSTHead;
public int maxSubBSTSize;
public int min;
public int max;
public Info(TreeNode h, int size, int mi, int ma) {
maxSubBSTHead = h;
maxSubBSTSize = size;
min = mi;
max = ma;
}
}
针对每一颗子树，都有如上结构信息，其中
maxSubBSTHead: 表示某个子树的最大二叉搜索子树的头结点
maxSubBSTSize: 表示某个结点如果是二叉搜索树，其大小为多少
min：表示以某个结点为头的树的最小值是多少
max：表示以某个结点为头的树的最大值是多少
接下来定义递归函数
Info process(TreeNode X)
以 X 为头的树，返回对应的 Info
接下来整理可能性
-
如果
X == null则直接返回null，即 base case； -
接下来问左树要 Info 信息，再问右树要 Info 信息，整合成 head 的 info 信息，以代码注释来说明
// 问左树要信息
Info leftInfo = process(X.left);
// 问右树要信息
Info rightInfo = process(X.right);
int min = X.val;
int max = X.val;
TreeNode maxSubBSTHead = null;
int maxSubBSTSize = 0;
if (leftInfo != null) {
// 左树信息不为 null
// 则 head.val 和 左树的min PK，谁小谁是以head 为头的min 信息
min = Math.min(min, leftInfo.min);
// 则 head.val 和 左树的max PK，谁大谁是以head 为头的max 信息
max = Math.max(max, leftInfo.max);
// 以 head 为头的最大二叉搜索子树的头结点至少是leftInfo.maxSubBSTHead
maxSubBSTHead = leftInfo.maxSubBSTHead;
// 以 head 为头的最大二叉搜索子树的头结点大小至少是leftInfo.maxSubBSTSize
maxSubBSTSize = leftInfo.maxSubBSTSize;
}
if (rightInfo != null) {
// 右树信息不为 null
// 思路和 左树信息不为 null 一样
min = Math.min(min, rightInfo.min);
max = Math.max(max, rightInfo.max);
if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
maxSubBSTHead = rightInfo.maxSubBSTHead;
maxSubBSTSize = rightInfo.maxSubBSTSize;
}
}
// 到了这一步，说明 leftInfo 和 rightInfo 至少有一个为 null
// 不管哪个为null，如果要以 X 为最大二叉搜索子树的头结点，则需要满足以下条件
// 1. leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.val
// 2. rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.val
if ((leftInfo == null || (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.val))
&& (rightInfo == null || (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.val))) {
maxSubBSTHead = X;
maxSubBSTSize =
(leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
+ 1;
}
return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
两个思路完整代码如下（含测试代码）
import java.util.ArrayList;
public class Code_MaxSubBSTHead {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int data) {
this.val = data;
}
}
public static int getBSTSize(TreeNode head) {
if (head == null) {
return 0;
}
ArrayList arr = new ArrayList<>();
in(head, arr);
for (int i = 1; i < arr.size(); i++) {
if (arr.get(i).val <= arr.get(i - 1).val) {
return 0;
}
}
return arr.size();
}
public static void in(TreeNode head, ArrayList arr) {
if (head == null) {
return;
}
in(head.left, arr);
arr.add(head);
in(head.right, arr);
}
public static TreeNode maxSubBSTHead1(TreeNode head) {
if (head == null) {
return null;
}
if (getBSTSize(head) != 0) {
return head;
}
TreeNode leftAns = maxSubBSTHead1(head.left);
TreeNode rightAns = maxSubBSTHead1(head.right);
return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
}
public static TreeNode maxSubBSTHead2(TreeNode head) {
if (head == null) {
return null;
}
return process(head).maxSubBSTHead;
}
// 每一棵子树
public static class Info {
public TreeNode maxSubBSTHead;
public int maxSubBSTSize;
public int min;
public int max;
public Info(TreeNode h, int size, int mi, int ma) {
maxSubBSTHead = h;
maxSubBSTSize = size;
min = mi;
max = ma;
}
}
public static Info process(TreeNode X) {
if (X == null) {
return null;
}
Info leftInfo = process(X.left);
Info rightInfo = process(X.right);
int min = X.val;
int max = X.val;
TreeNode maxSubBSTHead = null;
int maxSubBSTSize = 0;
if (leftInfo != null) {
min = Math.min(min, leftInfo.min);
max = Math.max(max, leftInfo.max);
maxSubBSTHead = leftInfo.maxSubBSTHead;
maxSubBSTSize = leftInfo.maxSubBSTSize;
}
if (rightInfo != null) {
min = Math.min(min, rightInfo.min);
max = Math.max(max, rightInfo.max);
if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
maxSubBSTHead = rightInfo.maxSubBSTHead;
maxSubBSTSize = rightInfo.maxSubBSTSize;
}
}
if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.val))
&& (rightInfo == null
? true
: (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.val))) {
maxSubBSTHead = X;
maxSubBSTSize =
(leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
+ 1;
}
return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
}
// for test
public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static TreeNode generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
TreeNode head = new TreeNode((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
public static void main(String[] args) {
int maxLevel = 4;
int maxValue = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
TreeNode head = generateRandomBST(maxLevel, maxValue);
if (maxSubBSTHead1(head) != maxSubBSTHead2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}