【题目3】
给定一颗二叉树的头结点head,返回这颗二叉树中最大的二叉搜索子树的大小
搜索二叉树定义:整棵树上没有重复值,左树比头结点小,右树比头结点大,每颗子树都如此。比如如下这棵树就是搜索二叉树但是在一棵二叉树中,未必全部都是搜索二叉树,比如如下这棵树,上图这棵树中的最大二叉搜索子树是以4为头结点的子树,而不是以3为头结点的子树。
此题还可以改为求一颗二叉树中最大二叉搜索子树的结点数量。
所以接下来列可能性(二叉树的递归套路最关键的地方就是列可能性):
第一种可能性:与X结点无关:要找的最大二叉搜索子树不以X结点为头结点,所以需要的信息就是,1)左树上满足条件的最大二叉搜索子树的大小 || 2)右树上满足条件的最大二叉树搜索子树的大小(大小结束结点个数)
第二种可能性:与X结点有关:要找的最大二叉搜索子树以X结点为头结点, 所以需要的信息就是,1)左树整体是搜索二叉树 && 2)右树整体是搜索二叉树 && 3)左树上的最大值<X && 4)右树上的最小值>X。
那么左树和右树最终需要的信息是哪些?
左树:1)左树上最大二叉搜索子树的大小,2)左树整体是否为搜索二叉树,3)左树上的最大值
右树:1)右树上最大二叉搜索子树的大小,2)右树整体是否为搜索二叉树,3)右树上的最小值
隐含信息:如果左树整体就是搜索二叉树,那么左树上最大二叉搜索子树大小就是整颗子树的大小,也就是左树的大小!!!右树也一样!!!
这种情况下左树和右树的要求不一样,所以需要求全集。因为递归函数根本不要对左树的要求和右树的要求做区分。只要一劳永逸地写一份代码套上所有的东西,所以对左树和右树的要求编成一样的就行了。
所以只要是子树,都需要返回4个信息:
最大二叉搜索子树的大小
子树整体是否是搜索二叉树
整棵子树的最大值
整颗子树的最小值
// 任何子树都需要返回的信息 public static class Info{ public boolean isAllBST;// 整体是否是搜索二叉树 public int maxSubBSTSize;// 最大二叉搜索子树的大小 public int max;// 整棵树的最大值 public int min;// 整棵树的最小值 public Info(boolean is,int size,int ma,int mi){ isAllBST=is; maxSubBSTSize=size; max=ma; min=mi; } }
完整代码:
package com.harrison.class08; import java.util.ArrayList; public class Code03_MaxSubBSTSize { 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 boolean isAllBST;// 整体是否是搜索二叉树 public int maxSubBSTSize;// 最大二叉搜索子树的大小 public int max;// 整棵树的最大值 public int min;// 整棵树的最小值 public Info(boolean is, int size, int ma, int mi) { isAllBST = is; 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);// 假设右树可以返回四个信息 // head结点的值在整棵树上,需要参与决策整棵树上的最大值和最小值 int max=head.value; int min=head.value; // 左树不为空的话,左树上的最大值可以参与决策整棵树上的最大值 // 同理,左树上的最小值也可以参与决策整棵树上的最小值,右树上也这么干 if(leftInfo!=null) { max=Math.max(max, leftInfo.max); min=Math.min(min, leftInfo.min); } if(rightInfo!=null) { max=Math.max(max, rightInfo.max); min=Math.min(min, rightInfo.min); } // 第一种可能性:与head节点无关,要找的最大二叉搜索子树不以head为头结点 // 所以这中情况下,左树和右树上的信息都能用 int maxSubBSTSize=0;// 先默认整颗树的最大二叉搜索子树大小为0 if(leftInfo!=null) {// 左树不为空的话,左树的答案就是目前的答案 maxSubBSTSize=leftInfo.maxSubBSTSize; } if(rightInfo!=null) {// 右树不为空的话,当前答案和右树上的答案取最大值 maxSubBSTSize=Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize); } // 第二种可能性,先假设不成立 boolean isAllBST=false; // 如果可能性2成立,就设置两个变量 // maxSubBSTSize=以head为头的所有结点数 // isAllBST=true // 因为可能性2成立的话,整棵树就是二叉搜索树 // 左树为空左树必是搜索二叉树,不为空的话,拿左树上的信息来用,右树同理 // 左树为空并不影响二叉搜索树的性质,为空则拿左树的信息来用,右树同理 if( (leftInfo==null?true:leftInfo.isAllBST) && (rightInfo==null?true:rightInfo.isAllBST) && (leftInfo==null?true:leftInfo.max<head.value) && (rightInfo==null?true:rightInfo.min>head.value) ) { // 左树整体已经是搜索二叉树的话,左树上最大二叉搜索子树的大小就是左树的大小 // 右树同理 maxSubBSTSize=(leftInfo==null?0:leftInfo.maxSubBSTSize) + (rightInfo==null?0:rightInfo.maxSubBSTSize) + 1; isAllBST=true; } return new Info(isAllBST,maxSubBSTSize,max,min); } public static int maxSubBSTSize1(Node head) { if(head==null) { return 0; } return process1(head).maxSubBSTSize; } 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 int maxSubBSTSize2(Node head) { if (head == null) { return 0; } int h = getBSTSize(head); if (h != 0) { return h; } return Math.max(maxSubBSTSize2(head.left), maxSubBSTSize2(head.right)); } 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 (maxSubBSTSize1(head) != maxSubBSTSize2(head)) { System.out.println("Oops!"); } } System.out.println("finish!"); } }