forked from dairongpeng/algorithm-note
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path08.md
More file actions
1329 lines (1111 loc) · 34.6 KB
/
08.md
File metadata and controls
1329 lines (1111 loc) · 34.6 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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
- [1 二叉树的递归套路](#1)
* [1.1 二叉树的递归套路深度实践](#11)
+ [1.1.1 例一：判断二叉树平衡与否](#111)
+ [1.1.2 例二：返回二叉树任意两个节点最大值](#112)
+ [1.1.3 例三：返回二叉树中的最大二叉搜索树Size](#113)
+ [1.1.4 例四：派对最大快乐值](#114)
+ [1.1.5 例五：判断二叉树是否是满二叉树](#115)
+ [1.1.6 例六：二叉搜索树的头结点](#116)
+ [1.1.7 例子七：是否是完全二叉树](#117)
+ [1.1.8 例子八：最低公共祖先](#118)
<h1 id='1'>1 二叉树的递归套路</h1>
1、 可以解决面试中的绝大部分二叉树(95%以上)的问题，尤其是树形dp问题
2、 其本质是利用递归遍历二叉树的便利性，每个节点在递归的过程中可以回到该节点3次
==具体步骤为：==
1. 假设以X节点为头，假设可以向X左树和右树要任何信息
2. 在上一步的假设下，讨论以X为头结点的树，得到答案的可能性（最重要），常见分类是与X无关的答案，与X有关的答案
3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4. 把左树信息和右树信息求全集，就是任何一颗子树都需要返回的信息S
5. 递归函数都返回S，每颗子树都这么要求
6. 写代码，在代码中考虑如何把左树信息和右树信息整合出整棵树的信息
<h2 id='11'>1.1 二叉树的递归套路深度实践</h2>
<h3 id='111'>1.1.1 例一：判断二叉树平衡与否</h3>
给定一棵二叉树的头结点head，返回这颗二叉树是不是平衡二叉树
> 平衡树概念：在一棵二叉树中，每一个子树，左树的高度和右树的高度差不超过1
> 那么如果以X为头的这颗树，要做到平衡，那么X的左树要是平衡的，右树也是平衡的，且X的左树高度和右树高度差不超过1
> 所以该题，我们X需要向左右子树要的信息为，1.高度 2. 是否平衡
```Java
package class08;
public class Code01_IsBalanced {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isBalanced1(Node head) {
boolean[] ans = new boolean[1];
ans[0] = true;
process1(head, ans);
return ans[0];
}
public static int process1(Node head, boolean[] ans) {
if (!ans[0] || head == null) {
return -1;
}
int leftHeight = process1(head.left, ans);
int rightHeight = process1(head.right, ans);
if (Math.abs(leftHeight - rightHeight) > 1) {
ans[0] = false;
}
return Math.max(leftHeight, rightHeight) + 1;
}
public static boolean isBalanced2(Node head) {
return process2(head).isBalaced;
}
// 左、右要求一样，Info 表示信息返回的结构体
public static class Info {
// 是否平衡
public boolean isBalaced;
// 高度多少
public int height;
public Info(boolean b, int h) {
isBalaced = b;
height = h;
}
}
// 递归调用，X自身也要返回信息Info。
// 解决X节点(当前节点)怎么返回Info信息
public static Info process2(Node X) {
// base case
if (X == null) {
return new Info(true, 0);
}
// 得到左树信息
Info leftInfo = process2(X.left);
// 得到右树信息
Info rightInfo = process2(X.right);
// 高度等于左右最大高度，加上当前头结点的高度1
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isBalanced = true;
// 左树不平衡或者右树不平衡，或者左右两子树高度差超过1
// 那么当前节点为头的树，不平衡
if (!leftInfo.isBalaced || !rightInfo.isBalaced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
isBalanced = false;
}
// 加工出当前节点的信息返回
return new Info(isBalanced, height);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
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 = 5;
int maxValue = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (isBalanced1(head) != isBalanced2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
```
<h2 id='112'>1.1.2 例二：返回二叉树任意两个节点最大值</h2>
给定一棵二叉树的头结点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
> 1、有可能最大距离和当前节点X无关，即最大距离是X左树的最大距离，或者右树的最大距离
> 2、最大距离跟X有关，即最大距离通过X。左树离X最远的点，到X右树上离X最远的点。即X左树的高度加上X自身高度1，加上X右树上的高度
> 结论：那么根据递归套路，我们每次递归，需要返回X左树的最大距离和高度，同理返回X右树的最大距离和高度。Info包含最大距离和高度
```Java
package class08;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class Code08_MaxDistance {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static int maxDistance1(Node head) {
if (head == null) {
return 0;
}
ArrayList<Node> arr = getPrelist(head);
HashMap<Node, Node> parentMap = getParentMap(head);
int max = 0;
for (int i = 0; i < arr.size(); i++) {
for (int j = i; j < arr.size(); j++) {
max = Math.max(max, distance(parentMap, arr.get(i), arr.get(j)));
}
}
return max;
}
public static ArrayList<Node> getPrelist(Node head) {
ArrayList<Node> arr = new ArrayList<>();
fillPrelist(head, arr);
return arr;
}
public static void fillPrelist(Node head, ArrayList<Node> arr) {
if (head == null) {
return;
}
arr.add(head);
fillPrelist(head.left, arr);
fillPrelist(head.right, arr);
}
public static HashMap<Node, Node> getParentMap(Node head) {
HashMap<Node, Node> map = new HashMap<>();
map.put(head, null);
fillParentMap(head, map);
return map;
}
public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
if (head.left != null) {
parentMap.put(head.left, head);
fillParentMap(head.left, parentMap);
}
if (head.right != null) {
parentMap.put(head.right, head);
fillParentMap(head.right, parentMap);
}
}
public static int distance(HashMap<Node, Node> parentMap, Node o1, Node o2) {
HashSet<Node> o1Set = new HashSet<>();
Node cur = o1;
o1Set.add(cur);
while (parentMap.get(cur) != null) {
cur = parentMap.get(cur);
o1Set.add(cur);
}
cur = o2;
while (!o1Set.contains(cur)) {
cur = parentMap.get(cur);
}
Node lowestAncestor = cur;
cur = o1;
int distance1 = 1;
while (cur != lowestAncestor) {
cur = parentMap.get(cur);
distance1++;
}
cur = o2;
int distance2 = 1;
while (cur != lowestAncestor) {
cur = parentMap.get(cur);
distance2++;
}
return distance1 + distance2 - 1;
}
public static int maxDistance2(Node head) {
return process(head).maxDistance;
}
// 我们的信息，整棵树的最大距离和整棵树的高度
public static class Info {
public int maxDistance;
public int height;
public Info(int dis, int h) {
maxDistance = dis;
height = h;
}
}
// 以X节点为头
public static Info process(Node X) {
// base case
if (X == null) {
return new Info(0, 0);
}
// 默认从左树拿到我们需要的info
Info leftInfo = process(X.left);
// 默认从右树拿到我们需要的info
Info rightInfo = process(X.right);
// 用左右树的信息，加工自身的info
// 自身的高度是，左右较大的高度加上自身节点高度1
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// 自身最大距离，是左右树最大距离和左右树高度相加再加1，求最大值
int maxDistance = Math.max(
Math.max(leftInfo.maxDistance, rightInfo.maxDistance),
leftInfo.height + rightInfo.height + 1);
// 自身的info返回
return new Info(maxDistance, height);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
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 (maxDistance1(head) != maxDistance2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
```
<h3 id='113'>1.1.3 例三：返回二叉树中的最大二叉搜索树Size</h3>
给定一颗二叉树的头结点head，返回这颗二叉树中最大的二叉搜索树的Size
> 搜索二叉树概念：整颗树上没有重复值，左树的值都比我小，右树的值都比我大。每颗子树都如此。
> 递归套路。1、与当前节点X无关，即最终找到的搜索二叉树，不以X为头
> 2、与X有关，那么X的左树整体是搜索二叉树，右树同理，且左树的最大值小于X,右树的最小值大于X
```Java
package class08;
import java.util.ArrayList;
public class Code04_MaxSubBSTSize {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
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 maxSubBSTSize1(Node head) {
if (head == null) {
return 0;
}
int h = getBSTSize(head);
if (h != 0) {
return h;
}
return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
}
public static int maxSubBSTSize2(Node head) {
if (head == null) {
return 0;
}
return process(head).maxSubBSTSize;
}
// public static Info process(Node head) {
// if (head == null) {
// return null;
// }
// Info leftInfo = process(head.left);
// Info rightInfo = process(head.right);
// int min = head.value;
// int max = head.value;
// int maxSubBSTSize = 0;
// if (leftInfo != null) {
// min = Math.min(min, leftInfo.min);
// max = Math.max(max, leftInfo.max);
// maxSubBSTSize = Math.max(maxSubBSTSize, leftInfo.maxSubBSTSize);
// }
// if (rightInfo != null) {
// min = Math.min(min, rightInfo.min);
// max = Math.max(max, rightInfo.max);
// maxSubBSTSize = Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize);
// }
// boolean isBST = false;
// if ((leftInfo == null ? true : (leftInfo.isAllBST && leftInfo.max < head.value))
// && (rightInfo == null ? true : (rightInfo.isAllBST && rightInfo.min > head.value))) {
// isBST = true;
// maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
// + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
// }
// return new Info(isBST, maxSubBSTSize, min, max);
// }
// 任何子树,都返回4个信息
public static class Info {
// 整体是否是二叉搜索树
public boolean isAllBST;
// 最大的满足二叉搜索树树条件的size
public int maxSubBSTSize;
// 整棵树的最小值
public int min;
// 整棵树的最大值
public int max;
public Info(boolean is, int size, int mi, int ma) {
isAllBST = is;
maxSubBSTSize = size;
min = mi;
max = ma;
}
}
// 以X为头
public static Info process(Node X) {
// base case
if(X == null) {
return null;
}
// 默认左树可以给我info信息
Info leftInfo = process(X.left);
// 默认右树可以给我info信息
Info rightInfo = process(X.right);
// 通过左右树给我的信息，加工我自己的info
int min = X.value;
int max = X.value;
// 左树不为空，加工min和max
if(leftInfo != null) {
min = Math.min(min, leftInfo.min);
max = Math.max(max, leftInfo.max);
}
// 右树不为空，加工min和max
if(rightInfo != null) {
min = Math.min(min, rightInfo.min);
max = Math.max(max, rightInfo.max);
}
// 可能性1与X无关的情况
int maxSubBSTSize = 0;
if(leftInfo != null) {
maxSubBSTSize = leftInfo.maxSubBSTSize;
}
if(rightInfo !=null) {
maxSubBSTSize = Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize);
}
// 可能性2，与X有关
boolean isAllBST = false;
if(
// 左树和人右树整体需要是搜索二叉树
( leftInfo == null ? true : leftInfo.isAllBST )
&&
( rightInfo == null ? true : rightInfo.isAllBST )
&&
// 左树最大值<X，右树最小值>X
(leftInfo == null ? true : leftInfo.max < X.value)
&&
(rightInfo == null ? true : rightInfo.min > X.value)
) {
maxSubBSTSize =
(leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
+
(rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
+
1;
isAllBST = true;
}
return new Info(isAllBST, maxSubBSTSize, min, max);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
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!");
}
}
```
<h3 id='114'>1.1.4 例四：派对最大快乐值</h3>
排队最大快乐值问题，员工信息定义如下，多叉树结构：
```Java
class Employee{
// 这名员工可以带来的快乐值
public int happy;
// 这名员工有哪些直接的下级
List<Employee> subordinates;
}
```
每个员工都符合Employee类的描述，整个公司的人员结构可以看作是一颗标准的，没有环的多叉树。树的头结点是公司唯一的老板。除了老板外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工（subordinates为空），除了基层员工股外，每个员工都有一个或多个直接下级。
现在公司要来办party，你可以决定哪些员工来，哪些员工不来，规则:
1、 如果某个员工来了，那么这个员工的所有直接下级都不能来
2、 排队的整体快乐值是所有到场员工的快乐值的累加
3、 你的目标是让排队的整体快乐值尽量的大
给定一颗多叉树头结点boss，请返回排队的最大快乐值
> 思路：根据X来与不来分类
> 如果X来，我们能获得X的快乐值X.happy。X的直接子不能来，但我们能拿到X某个子树整棵树的的最大快乐值
> 如果X不来，不发请柬，我们能获得X的快乐值为0，X直接子树头结点来或者不来求最大值...
```Java
package class08;
import java.util.ArrayList;
import java.util.List;
public class Code09_MaxHappy {
// 员工对应的多叉树节点结构
public static class Employee {
public int happy;
public List<Employee> nexts;
public Employee(int h) {
happy = h;
nexts = new ArrayList<>();
}
}
public static int maxHappy1(Employee boss) {
if (boss == null) {
return 0;
}
return process1(boss, false);
}
public static int process1(Employee cur, boolean up) {
if (up) {
int ans = 0;
for (Employee next : cur.nexts) {
ans += process1(next, false);
}
return ans;
} else {
int p1 = cur.happy;
int p2 = 0;
for (Employee next : cur.nexts) {
p1 += process1(next, true);
p2 += process1(next, false);
}
return Math.max(p1, p2);
}
}
public static int maxHappy2(Employee boss) {
if (boss == null) {
return 0;
}
Info all = process2(boss);
return Math.max(all.yes, all.no);
}
// 递归信息
public static class Info {
// 头结点在来的情况下整棵树的最大值
public int yes;
// 头结点在不来的情况下整棵树的最大值
public int no;
public Info(int y, int n) {
yes = y;
no = n;
}
}
public static Info process2(Employee x) {
// base case 基层员工
if (x.nexts.isEmpty()) {
return new Info(x.happy, 0);
}
// 当前X来的初始值
int yes = x.happy;
// 当前X不来的初始值
int no = 0;
// 每棵子树调用递归信息
for (Employee next : x.nexts) {
Info nextInfo = process2(next);
// 根据子树的递归返回的信息，加工自身的info
// 如果X来，子不来
yes += nextInfo.no;
// 如果X不来，子不确定来不来
no += Math.max(nextInfo.yes, nextInfo.no);
}
return new Info(yes, no);
}
// for test
public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
if (Math.random() < 0.02) {
return null;
}
Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
return boss;
}
// for test
public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
if (level > maxLevel) {
return;
}
int nextsSize = (int) (Math.random() * (maxNexts + 1));
for (int i = 0; i < nextsSize; i++) {
Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
e.nexts.add(next);
genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
}
}
public static void main(String[] args) {
int maxLevel = 4;
int maxNexts = 7;
int maxHappy = 100;
int testTimes = 100000;
for (int i = 0; i < testTimes; i++) {
Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
if (maxHappy1(boss) != maxHappy2(boss)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
```
<h3 id='115'>1.1.5 例五：判断二叉树是否是满二叉树</h3>
给定一棵二叉树的头结点head，返回这颗二叉树是不是满二叉树。
> 思路：满二叉树一定满足2^L - 1 == N，其中L是这颗二叉树的高度，N是这颗二叉树的节点个数
```Java
package class08;
public class Code02_IsFull {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isFull1(Node head) {
if (head == null) {
return true;
}
int height = h(head);
int nodes = n(head);
return (1 << height) - 1 == nodes;
}
public static int h(Node head) {
if (head == null) {
return 0;
}
return Math.max(h(head.left), h(head.right)) + 1;
}
public static int n(Node head) {
if (head == null) {
return 0;
}
return n(head.left) + n(head.right) + 1;
}
public static boolean isFull2(Node head) {
if (head == null) {
return true;
}
// 如果满足公式是满二叉树
Info all = process(head);
return (1 << all.height) - 1 == all.nodes;
}
// 信息
public static class Info {
public int height;
public int nodes;
public Info(int h, int n) {
height = h;
nodes = n;
}
}
// 递归套路
public static Info process(Node head) {
if (head == null) {
return new Info(0, 0);
}
Info leftInfo = process(head.left);
Info rightInfo = process(head.right);
// 高度
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// 节点数
int nodes = leftInfo.nodes + rightInfo.nodes + 1;
return new Info(height, nodes);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
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 = 5;
int maxValue = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (isFull1(head) != isFull2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
```
<h3 id='116'>1.1.6 例六：二叉搜索树的头结点</h3>
给定一棵二叉树的头结点head，返回这颗二叉树中最大的二叉搜索子树的头节点
> 和前文的返回二叉搜索子树的Size问题类似
```Java
package class08;
import java.util.ArrayList;
public class Code05_MaxSubBSTHead {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
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 maxSubBSTHead1(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 maxSubBSTHead2(Node head) {
if (head == null) {
return null;
}
return process(head).maxSubBSTHead;
}
// 每一棵子树Info
public static class Info {
public Node maxSubBSTHead;
public int maxSubBSTSize;
public int min;
public int max;
public Info(Node h, int size, int mi, int ma) {
maxSubBSTHead = h;
maxSubBSTSize = size;
min = mi;
max = ma;
}
}
public static Info process(Node X) {
if (X == null) {
return null;
}
Info leftInfo = process(X.left);
Info rightInfo = process(X.right);
int min = X.value;
int max = X.value;
Node maxSubBSTHead = null;
int maxSubBSTSize = 0;
if (leftInfo != null) {
min = Math.min(min, leftInfo.min);
max = Math.max(max, leftInfo.max);
maxSubBSTHead = leftInfo.maxSubBSTHead;
maxSubBSTSize = leftInfo.maxSubBSTSize;
}
if (rightInfo != null) {
min = Math.min(min, rightInfo.min);
max = Math.max(max, rightInfo.max);
if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
maxSubBSTHead = rightInfo.maxSubBSTHead;
maxSubBSTSize = rightInfo.maxSubBSTSize;
}
}
if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.value))
&& (rightInfo == null ? true : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.value))) {
maxSubBSTHead = X;
maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
}
return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
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!");
}
}
```
<h3 id='117'>1.1.7 例子七：是否是完全二叉树</h3>
给定一棵二叉树的头结点head，返回这颗二叉树是不是完全二叉树
> 完全二叉树概念在堆的章节，有介绍。
> 宽度优先遍历解决思路:
1、如果用树的宽度优先遍历的话，如果某个节点有右孩子，但是没有左孩子，一定不是完全二叉树
2、在1条件的基础上，一旦遇到第一个左右孩子不双全的节点，后续所有节点必须为叶子节点
> 二叉树递归套路解法思路：
1、满二叉树（无缺口），一定是完全二叉树。此时左右树需要给X的信息是，是否是满的和高度。如果左右树满，且左右树高度一样，那么是该种情况--满二叉树
2、有缺口，1缺口可能停在我的左树上。左树需要给我是否是完全二叉树，右树需要给X是否是满二叉树，且左树高度比右树高度大1
3、缺口可能在左右树的分界。左树是满的，右树也是满的，左树高度比右树大1
4、左树已经满了，缺口可能在我的右树上。左树是满的，右树是完全二叉树，且左右树高度一样
==所以我们的递归时，需要向子树要的信息为：是否是完全二叉树，是否是满二叉树，高度==
```Java
package class08;
import java.util.LinkedList;
public class Code06_IsCBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 宽度优先遍历解决方法
public static boolean isCBT1(Node head) {
if (head == null) {
return true;
}
LinkedList<Node> queue = new LinkedList<>();
// 是否遇到过左右两个孩子不双全的节点
boolean leaf = false;