[数据结构与算法]二叉树的递归套路——最大二叉搜索子树头结点

给定一颗二叉树的头结点head，返回这颗二叉树中最大的二叉搜索子树的头结点

此题跟这篇文章解题思路类似——二叉树的递归套路——最大二叉搜索子树大小

第一种可能性：与X无关，就是说以X为头结点的左树上有一颗子树是最大搜索二叉树；或者以X为头结点的右树上有一颗子树是最大搜索二叉树。 两边谁大就返回那边子树的头结点。

第二种可能性：与X有关（以X为头节点），则需要：
左树整体是搜索二叉树
&&
右树整体是搜索二叉树
&&
左树上的最大值<头节点
&&
右树上的最小值>头节点

所以每颗子树需要返回的信息就是：

1. 整颗子树上最大二叉搜索子树的头节点
2. 整颗子树上最大二叉搜索子树的大小（为什么需要大小，因为需要通过比较大小返回大的那一个）
3. 整颗子树整体是否为搜索二叉树（但是此条信息可以通过第一条信息得出，如果在一棵子树上，最大二叉搜索子树的头节点就是子树的头节点，意味着整颗子树就是搜索二叉树）
4. 整颗子树上的最大值
5. 整颗子树上的最小值

所以不用额外设置一个boolean类型变量来标记整颗子树是否为搜索二叉树

public static class Info{
		public Node maxSubBSTHead;
		//public boolean isAllBST;
		public int maxSubBSTSize;
		public int max;
		public int min;
		
		public Info(Node h,int size,int ma,int mi) {
			maxSubBSTHead=h;
			maxSubBSTSize=size;
			max=ma;
			min=mi;
		}
	}

完整代码：

package com.harrison.class08;

import java.util.ArrayList;

public class Code07_MaxSubBSTHead {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}
	
	public static class Info{
		public Node maxSubBSTHead;
		public int maxSubBSTSize;
		public int max;
		public int min;
		
		public Info(Node h,int size,int ma,int mi) {
			maxSubBSTHead=h;
			maxSubBSTSize=size;
			max=ma;
			min=mi;
		}
	}
	
	public static Info process1(Node head) {
		if(head==null) {
			return null;
		}
		Info leftInfo=process1(head.left);
		Info rightInfo=process1(head.right);
		Node maxSubBSTHead=null;
		int maxSubBSTSize=0;
		int max=head.value;
		int min=head.value;
		if(leftInfo!=null) {
			max=Math.max(max, leftInfo.max);
			min=Math.min(min, leftInfo.min);
			maxSubBSTHead=leftInfo.maxSubBSTHead;
			maxSubBSTSize=leftInfo.maxSubBSTSize;
		}
		if(rightInfo!=null) {
			max=Math.max(max, rightInfo.max);
			min=Math.min(min, rightInfo.min);
			if(rightInfo.maxSubBSTSize>maxSubBSTSize) {
				maxSubBSTSize=rightInfo.maxSubBSTSize;
				maxSubBSTHead=rightInfo.maxSubBSTHead;
			}
		}
		// 如果在一棵子树上，最大二叉搜索子树的头节点就是子树的头节点，意味着整颗子树就是搜索二叉树
		if(
			(leftInfo==null?true:(leftInfo.maxSubBSTHead==head.left))
			&&
			(rightInfo==null?true:(rightInfo.maxSubBSTHead==head.right))
			&&
			(leftInfo==null?true:leftInfo.max<head.value)
			&&
			(rightInfo==null?true:rightInfo.min>head.value)
		  ) {
			maxSubBSTHead=head;
			maxSubBSTSize=(
							(leftInfo==null?0:leftInfo.maxSubBSTSize)
							+
							(rightInfo==null?0:rightInfo.maxSubBSTSize)
							+1
					      );
		}
		return new Info(maxSubBSTHead, maxSubBSTSize, max, min);
	}
	
	public static Node maxSubBSTHead1(Node head) {
		if(head==null) {
			return null;
		}
		return process1(head).maxSubBSTHead;
	}
	
	public static int getBSTSize(Node head) {
		if (head == null) {
			return 0;
		}
		ArrayList<Node> 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<Node> arr) {
		if (head == null) {
			return;
		}
		in(head.left, arr);
		arr.add(head);
		in(head.right, arr);
	}

	public static Node maxSubBSTHead2(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 generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	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!");
	}
}