-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBiggestSubBSTInTree.java
More file actions
176 lines (155 loc) · 6.05 KB
/
Copy pathBiggestSubBSTInTree.java
File metadata and controls
176 lines (155 loc) · 6.05 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
package tree;
import org.junit.Test;
/**
* @Author: wei1
* @Date: Create in 2018/12/5 13:21
* @Description: 求二叉树的最大搜索二叉子树
* 典型的树型的dp问题，分析需要返回的变量，通
* 过返回的变量推出本次递归需要返回的变量
* 1.左树是最大的搜索二叉树
* 2.右树是最大的搜索二叉树
* 3.本身就是最大的搜索二叉树
* 根据什么可以分析出上面的三种情况呢？
* 1>左树的size 左树的头节点 左树的最大值
* 2>右树的size 右树的头节点 右树的最大值
* 将1，2需要的合起来
*/
public class BiggestSubBSTInTree {
class ReturnType {
TreeNode head;
int size;
int max;
int min;
public ReturnType(TreeNode head, int size, int max, int min) {
this.head = head;
this.size = size;
this.max = max;
this.min = min;
}
}
public ReturnType process(TreeNode head) {
if (head == null) {
return new ReturnType(null, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
ReturnType leftReturn = process(head.left);
ReturnType rightReturn = process(head.right);
int headSize = 0;
if (head.left == leftReturn.head && head.right == rightReturn.head &&
head.val > leftReturn.max && head.val < rightReturn.min) {
headSize = leftReturn.size + 1 + rightReturn.size;
}
int p1 = leftReturn.size;
int p2 = rightReturn.size;
int maxSize = Math.max(Math.max(p1, p2), headSize);
TreeNode maxHead = leftReturn.size > rightReturn.size ? leftReturn.head : rightReturn.head;
if (maxSize == headSize) {
maxHead = head;
}
return new ReturnType(maxHead, maxSize, Math.max(Math.max(leftReturn.max, rightReturn
.max), head.val), Math.min(Math.min(leftReturn.min, rightReturn
.min), head.val));
}
//在写一遍最大的搜索二叉子树
public ReturnType bb(TreeNode head) {
if (head == null) {
return new ReturnType(null, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
ReturnType leftReturn = bb(head.left);
ReturnType rightReturn = bb(head.right);
if (head.left == leftReturn.head && head.right == rightReturn.head &&
head.val > leftReturn.max && head.val < rightReturn.min) {
return new ReturnType(head, leftReturn.size + rightReturn.size + 1, Math.max(Math.max
(leftReturn.max, rightReturn.max), head.val),
Math.min(Math.min(leftReturn.min, rightReturn.min), head.val));
} else {
return leftReturn.size > rightReturn.size ? leftReturn : rightReturn;
}
}
public static TreeNode bigTreeNode(TreeNode head) {
int[] record = new int[3]; // 0->size, 1->min, 2->max
return posOrder(head, record);
}
public static TreeNode posOrder(TreeNode head, int[] record) {
if (head == null) {
record[0] = 0;
record[1] = Integer.MAX_VALUE;
record[2] = Integer.MIN_VALUE;
return null;
}
int value = head.val;
TreeNode left = head.left;
TreeNode right = head.right;
TreeNode lBST = posOrder(left, record);
int lSize = record[0];
int lMin = record[1];
int lMax = record[2];
TreeNode 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;
}
public static void printTree(TreeNode head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(TreeNode head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.val + 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) {
TreeNode head = new TreeNode(6);
head.left = new TreeNode(1);
head.left.left = new TreeNode(0);
head.left.right = new TreeNode(3);
head.right = new TreeNode(12);
head.right.left = new TreeNode(10);
head.right.left.left = new TreeNode(4);
head.right.left.left.left = new TreeNode(2);
head.right.left.left.right = new TreeNode(5);
head.right.left.right = new TreeNode(14);
head.right.left.right.left = new TreeNode(11);
head.right.left.right.right = new TreeNode(15);
head.right.right = new TreeNode(13);
head.right.right.left = new TreeNode(20);
head.right.right.right = new TreeNode(16);
printTree(head);
ReturnType result1 = new BiggestSubBSTInTree().process(head);
// TreeNode result2 = bigTreeNode(head);
ReturnType result2 = new BiggestSubBSTInTree().bb(head);
printTree(result1.head);
printTree(result2.head);
System.out.println(result2.size);
}
@Test
public void test() {
System.out.println(1 ^ 2 ^ 3);
System.out.println(1 ^ 3 ^ 2);
System.out.println(2 ^ 3 ^ 1);
}
}