最大搜索子树
【摘要】 给定一个二叉树的头结点，返回最大搜索子树的大小。
我们先定义结点：
public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } }
分析：
直...
给定一个二叉树的头结点，返回最大搜索子树的大小。
我们先定义结点：
-
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
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）