求二叉树中最大的二叉搜索子树的头节点

作者：Grey

原文地址：

博客园：求二叉树中最大的二叉搜索子树的头节点

CSDN：求二叉树中最大的二叉搜索子树的头节点

题目描述

给定一棵二叉树的头节点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<TreeNode> 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.maxSubBSTHeadmaxSubBSTHead = leftInfo.maxSubBSTHead;// 以 head 为头的最大二叉搜索子树的头结点大小至少是leftInfo.maxSubBSTSizemaxSubBSTSize = 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.valif ((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<TreeNode> 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<TreeNode> 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 testpublic static TreeNode generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic 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!");}
}