最大搜索子树

给定一个二叉树的头结点，返回最大搜索子树的大小。

我们先定义结点：

      public static class Node {
     		public int value;
     		public Node left;
     		public Node right;
     		public Node(int data) {
     			this.value = data;
      		}
      	}
  
 

分析：

直接判断每个节点左边小右边大是不对滴

可以暴力判断所有的子树，就不说了。

最大搜索子树可能性：

第一种可能性，以node为头的结点的最大二叉搜索子树可能来自它左子树；
第二种可能性，以node为头的结点的最大二叉搜索子树可能来自它右子树；
第三种可能性，左树整体是搜索二叉树，右树整体也是搜索二叉树，而且左树的头是node.left，右树的头是node.right，且左树的最大值< node.value，右树的最小值 > node.value， 那么以我为头的整棵树都是搜索二叉树；
 

第三种可能性的判断，需要的信息有：左子树的最大值、右子树的最小值、左子树是不是搜索二叉树、右子树是不是搜索二叉树

还有左右搜索二叉树的最大深度。

我们判断了自己，并不知道自己是哪边的子树，我们要返回自己的最大值和最小值。

这样，定义一个返回类型：

      public static class ReturnType{
     		public int size;//最大搜索子树深度
     		public Node head;//最大搜索子树的根
     		public int min;//子树最小
     		public int max;//子树最大
     		public ReturnType(int a, Node b,int c,int d) {
     			this.size =a;
     			this.head = b;
     			this.min = c;
     			this.max = d;
      		}
      	}
  
 

然后开始写代码：

注意：

1）NULL返回深度0，头为NULL，最大值最小值返回系统最大和最小，这样才不会影响别的判断。

     	public static ReturnType process(Node head) {
     		if(head == null) {
     			return new ReturnType(0,null,Integer.MAX_VALUE, Integer.MIN_VALUE);
      		}
      		Node left = head.left;//取信息
      		ReturnType leftSubTressInfo = process(left);
      		Node right = head.right;
      		ReturnType rightSubTressInfo = process(right);
     		int includeItSelf = 0;
     		if(leftSubTressInfo.head == left // 左子树为搜索树
       &&rightSubTressInfo.head == right// 右子树为搜索树
       && head.value > leftSubTressInfo.max// 左子树最大值小于当前节点
       && head.value < rightSubTressInfo.min//右子树最小值大于当前节点
       ) {
      			includeItSelf = leftSubTressInfo.size + 1 + rightSubTressInfo.size;//当前节点为根的二叉树为搜索树
      		}
     		int p1 = leftSubTressInfo.size;
     		int p2 = rightSubTressInfo.size;
     		int maxSize = Math.max(Math.max(p1, p2), includeItSelf);//最大搜索树深度
      		Node maxHead = p1 > p2 ? leftSubTressInfo.head : rightSubTressInfo.head;
     		if(maxSize == includeItSelf) {
      			maxHead = head;
      		}//最大搜索树的根：来自左子树、来自右子树、本身
     		return new ReturnType(
       maxSize, //深度
       maxHead, //根
       Math.min(Math.min(leftSubTressInfo.min,rightSubTressInfo.min),head.value), //最小
       Math.max(Math.max(leftSubTressInfo.max,rightSubTressInfo.max),head.value));	//最大
      	}
  
 

可以进一步改进：

空间浪费比较严重

其实返回值为三个int，一个node，我们可以把三个int合起来，用全局数组记录，函数只返回node（搜索树的根）即可。

给出完整代码：

      public class BiggestSubBSTInTree {
     	public static class Node {
     		public int value;
     		public Node left;
     		public Node right;
     		public Node(int data) {
     			this.value = data;
      		}
      	}
     	public static Node biggestSubBST(Node head) {
     		int[] record = new int[3]; // 0->size, 1->min, 2->max
     		return posOrder(head, record);
      	}
     	public static class ReturnType{
     		public int size;//最大搜索子树深度
     		public Node head;//最大搜索子树的根
     		public int min;//子树最小
     		public int max;//子树最大
     		public ReturnType(int a, Node b,int c,int d) {
     			this.size =a;
     			this.head = b;
     			this.min = c;
     			this.max = d;
      		}
      	}
     	public static ReturnType process(Node head) {
     		if(head == null) {
     			return new ReturnType(0,null,Integer.MAX_VALUE, Integer.MIN_VALUE);
      		}
      		Node left = head.left;//取信息
      		ReturnType leftSubTressInfo = process(left);
      		Node right = head.right;
      		ReturnType rightSubTressInfo = process(right);
     		int includeItSelf = 0;
     		if(leftSubTressInfo.head == left // 左子树为搜索树
       &&rightSubTressInfo.head == right// 右子树为搜索树
       && head.value > leftSubTressInfo.max// 左子树最大值小于当前节点
       && head.value < rightSubTressInfo.min//右子树最小值大于当前节点
       ) {
      			includeItSelf = leftSubTressInfo.size + 1 + rightSubTressInfo.size;//当前节点为根的二叉树为搜索树
      		}
     		int p1 = leftSubTressInfo.size;
     		int p2 = rightSubTressInfo.size;
     		int maxSize = Math.max(Math.max(p1, p2), includeItSelf);//最大搜索树深度
      		Node maxHead = p1 > p2 ? leftSubTressInfo.head : rightSubTressInfo.head;
     		if(maxSize == includeItSelf) {
      			maxHead = head;
      		}//最大搜索树的根：来自左子树、来自右子树、本身
     		return new ReturnType(
       maxSize, //深度
       maxHead, //根
       Math.min(Math.min(leftSubTressInfo.min,rightSubTressInfo.min),head.value),   //最小
       Math.max(Math.max(leftSubTressInfo.max,rightSubTressInfo.max),head.value));	 //最大
      	}
     	public static Node posOrder(Node head, int[] record) {
     		if (head == null) {
      			record[0] = 0;
      			record[1] = Integer.MAX_VALUE;
      			record[2] = Integer.MIN_VALUE;
     			return null;
      		}
     		int value = head.value;
      		Node left = head.left;
      		Node right = head.right;
      		Node lBST = posOrder(left, record);
     		int lSize = record[0];
     		int lMin = record[1];
     		int lMax = record[2];
      		Node rBST = posOrder(right, record);
     		int rSize = record[0];
     		int rMin = record[1];
     		int rMax = record[2];
      		record[1] = Math.min(rMin, Math.min(lMin, value)); // lmin, value, rmin -> min 
      		record[2] = Math.max(lMax, Math.max(rMax, value)); // lmax, value, rmax -> max
     		if (left == lBST && right == rBST && lMax < value && value < rMin) {
      			record[0] = lSize + rSize + 1;//修改深度
     			return head; //返回根
      		}//满足当前构成搜索树的条件
      		record[0] = Math.max(lSize, rSize);//较大深度
     		return lSize > rSize ? lBST : rBST;//返回较大搜索树的根
      	}
     	// for test -- print tree
     	public static void printTree(Node head) {
      		System.out.println("Binary Tree:");
      		printInOrder(head, 0, "H", 17);
      		System.out.println();
      	}
     	public static void printInOrder(Node head, int height, String to, int len) {
     		if (head == null) {
     			return;
      		}
      		printInOrder(head.right, height + 1, "v", len);
      		String val = to + head.value + to;
     		int lenM = val.length();
     		int lenL = (len - lenM) / 2;
     		int lenR = len - lenM - lenL;
      		val = getSpace(lenL) + val + getSpace(lenR);
      		System.out.println(getSpace(height * len) + val);
      		printInOrder(head.left, height + 1, "^", len);
      	}
     	public static String getSpace(int num) {
      		String space = " ";
      		StringBuffer buf = new StringBuffer("");
     		for (int i = 0; i < num; i++) {
      			buf.append(space);
      		}
     		return buf.toString();
      	}
     	public static void main(String[] args) {
      		Node head = new Node(6);
      		head.left = new Node(1);
      		head.left.left = new Node(0);
      		head.left.right = new Node(3);
      		head.right = new Node(12);
      		head.right.left = new Node(10);
      		head.right.left.left = new Node(4);
      		head.right.left.left.left = new Node(2);
      		head.right.left.left.right = new Node(5);
      		head.right.left.right = new Node(14);
      		head.right.left.right.left = new Node(11);
      		head.right.left.right.right = new Node(15);
      		head.right.right = new Node(13);
      		head.right.right.left = new Node(20);
      		head.right.right.right = new Node(16);
      		printTree(head);
      		Node bst = biggestSubBST(head);
      		printTree(bst);
      	}
      }
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/84251431