给定一棵二叉树的根节点 root，返回这棵二叉树中最大的二叉搜索子树的根节点。
2、分析找到最大二叉搜索子树可见返回二叉树中最大的二叉搜索子树的大小，这里只是在求根节点，于是在Info 信息体中增加一个根节点的信息。
3、实现 C++版#includeJava 版#include #include using namespace std; class TreeNode { public: int value; TreeNode *left; TreeNode *right; TreeNode(int data) : value(data) {} }; //方法1 void inOrder(TreeNode *root, vector &arr) { if (root == nullptr) return ; inOrder(root->left, arr); arr.push_back(root); inOrder(root->right, arr); } int getBSTSize(TreeNode *root) { if (root == nullptr) return 0; vector arr; inOrder(root, arr); for (int i = 1; i < arr.size(); i++) { if (arr[i]->value <= arr[i - 1]->value) return 0; } return arr.size(); } TreeNode *maxSubBSTRoot1(TreeNode *root) { if (root == nullptr) return nullptr; if (getBSTSize(root) != 0) return root; TreeNode *leftAns = maxSubBSTRoot1(root->left); TreeNode *rightAns = maxSubBSTRoot1(root->right); return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns; } //方法2 class Info { public: TreeNode *maxSubBSTRoot; //最大二叉搜索子树的根节点 int maxSubBSTSize; //最大二叉搜索子树的节点数 int maxVal; int minVal; Info(TreeNode *root, int size, int ma, int mi) : maxSubBSTRoot(root), maxSubBSTSize(size), maxVal(ma), minVal(mi) {} }; Info *process(TreeNode *x) { if (x == nullptr) { return nullptr; } Info *leftInfo = process(x->left); Info *rightInfo = process(x->right); int maxVal = x->value; int minVal = x->value; int maxSubBSTSize = 0; TreeNode *maxSubBSTRoot = nullptr; if (leftInfo != nullptr) { maxVal = max(maxVal, leftInfo->maxVal); minVal = min(minVal, leftInfo->minVal); //可能性1：最大二叉搜索子树在左树上 maxSubBSTSize = leftInfo->maxSubBSTSize; maxSubBSTRoot = leftInfo->maxSubBSTRoot; } if (rightInfo != nullptr) { maxVal = max(maxVal, rightInfo->maxVal); minVal = min(minVal, rightInfo->minVal); //可能性2：最大二叉搜索子树在右树上 if (rightInfo->maxSubBSTSize > maxSubBSTSize) { maxSubBSTSize = rightInfo->maxSubBSTSize; maxSubBSTRoot = rightInfo->maxSubBSTRoot; } } //可能性3：整棵树是BST bool leftBST = leftInfo == nullptr ? true : (leftInfo->maxSubBSTRoot == x->left && leftInfo->maxVal < x->value); bool rightBST = rightInfo == nullptr ? true : (rightInfo->maxSubBSTRoot == x->right && rightInfo->minVal > x->value); if (leftBST && rightBST) { maxSubBSTRoot = x; maxSubBSTSize = (leftInfo == nullptr ? 0 : leftInfo->maxSubBSTSize) + (rightInfo == nullptr ? 0 : rightInfo->maxSubBSTSize) + 1; } return new Info(maxSubBSTRoot, maxSubBSTSize, maxVal, minVal); } TreeNode *maxSubBSTRoot2(TreeNode *root) { if (root == nullptr) return nullptr; return process(root)->maxSubBSTRoot; } //for test TreeNode *generate(int level, int maxl, int maxv) { if (level > maxl || (rand() % 100 / (double)101) < 0.5) return nullptr; TreeNode *root = new TreeNode(rand() % maxv); root->left = generate(level + 1, maxl, maxv); root->right = generate(level + 1, maxl, maxv); return root; } TreeNode *generateRandomBST(int level, int value) { return generate(1, level, value); } int main() { srand(time(0)); int maxLevel = 4; int maxValue = 100; int testTimes = 1000001; cout << "Test begin:" << endl; for (int i = 0; i < testTimes; i++) { TreeNode *root = generateRandomBST(maxLevel, maxValue); if (maxSubBSTRoot1(root) != maxSubBSTRoot2(root)) { cout << "Failed!" << endl; return 0; } if (i && i % 1000 == 0) cout << i << " cases passed!" << endl; } cout << "Success!!" << endl; return 0; }
import java.util.ArrayList;
public class MaxSubBSTHead {
public static class Node {
public int value;
Node left;
Node right;
public Node(int data) {
this.value = data;
}
}
//方法一：
public static int getBSTSize(Node 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).value <= arr.get(i - 1).value) {
return 0;
}
}
return arr.size();
}
public static void in(Node head, ArrayList arr) {
if (head == null) {
return;
}
in(head.left, arr);
arr.add(head);
in(head.right, arr);
}
public static Node maxSubBSTHead1(Node head) {
if (head == null) {
return null;
}
if (getBSTSize(head) != 0) {
return head;
}
Node leftAns = maxSubBSTHead1(head.left);
Node rightAns = maxSubBSTHead1(head.right);
return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
}
//方法二：递归套路
public static Node maxSubBSTHead2(Node head) {
if (head == null) return head;
return process(head).maxSubBSTHead;
}
public static class Info {
public Node maxSubBSTHead; //最大搜索子树的根节点
public int maxSubBSTSize;//最大搜索子树的节点数
public int max; //最大值
public int min; //最小值
public Info(Node head, int size, int ma, int mi) {
maxSubBSTHead = head;
maxSubBSTSize = size;
max = ma;
min = mi;
}
}
public static Info process(Node x) {
if (x == null) return null;
//获取左右树的信息
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
Node maxSubBSTHead = null;
int maxSubBSTSize = 0;
int max = x.value;
int min = x.value;
if (leftInfo != null) { //左树不为空
//更新最值
max = Math.max(max, leftInfo.max);
min = Math.min(min, leftInfo.min);
//可能性1：最大搜索二叉树在左树上
maxSubBSTHead = leftInfo.maxSubBSTHead;
maxSubBSTSize = leftInfo.maxSubBSTSize;
}
if (rightInfo != null) {
max = Math.max(max, rightInfo.max);
min = Math.min(min, rightInfo.min);
//可能性2：最大搜索二叉树在右树上，前提是如果右树的最大搜索子树的size > 左树的最大搜索子树的size
if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
maxSubBSTHead = rightInfo.maxSubBSTHead;
maxSubBSTSize = rightInfo.maxSubBSTSize;
}
}
//可能性3：整棵树是最大搜索二叉树
//如果左右子树的根恰好是最大搜索二叉树的根，那么X为根的二叉树就是最大搜索二叉树，x为其根
boolean leftBST = leftInfo == null ? true : (leftInfo.maxSubBSTHead == x.left && leftInfo.max < x.value);
boolean rightBST = rightInfo == null ? true : (rightInfo.maxSubBSTHead == x.right && rightInfo.min > x.value);
if (leftBST && rightBST) {
maxSubBSTHead = x;
maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
}
return new Info(maxSubBSTHead, maxSubBSTSize, max, min);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
Node head = new Node((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++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (maxSubBSTHead1(head) != maxSubBSTHead2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
