-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTreeChildSolution.java
More file actions
151 lines (116 loc) · 4.24 KB
/
TreeChildSolution.java
File metadata and controls
151 lines (116 loc) · 4.24 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
package tree;
import java.util.*;
public class TreeChildSolution {
int count = 0;
// 后序遍历 二叉树
public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length < 1) return false;
if (sequence.length == 1) return true;
int last = sequence[sequence.length - 1];
int max = firstPositionOfBiggerThanLast(sequence);
TreeSolution solution = new TreeSolution();
//截取 左子树
int[] left = solution.subArray(sequence, 0, max - 1);
// 截取 右子树
int[] right = solution.subArray(sequence, max, sequence.length - 2);
if (!checkTheRightPart(right, last)) {
return false;
}
boolean checkLeftSeq = left.length == 0 ? true : VerifySquenceOfBST(left);
boolean checkRightSeq = left.length == 0 ? true : VerifySquenceOfBST(right);
if (checkLeftSeq && checkRightSeq) {
return true;
} else {
return false;
}
}
// 返回第一个 比最后一个数字大的
public int firstPositionOfBiggerThanLast(int[] seq) {
int last = seq[seq.length - 1];
if (seq.length <= 1) {
return -1;
}
for (int i = 0; i < seq.length - 1; i++) {
if (seq[i] > last) {
return i;
}
}
return seq.length - 1;
}
// 检查 右子树 是否比最后一个数 都大
public boolean checkTheRightPart(int[] rightSeq, int last) {
for (int i = 0; i < rightSeq.length; i++) {
if (rightSeq[i] < last) {
return false;
}
}
return true;
}
// 递归判断 判断一颗树是否是平衡二叉树
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) return true;
if(!IsBalancedOfLR(root)) return false;
if(root.left !=null) return IsBalanced_Solution(root.left);
if(root.right!=null) return IsBalanced_Solution(root.right);
else return true;
}
// 判断左右子树是否平衡
public boolean IsBalancedOfLR(TreeNode root) {
if(root == null) return true;
int leftDepth = root.left == null? 0: TreeDepth(root.left);
count = 0;
int rightDepth = root.right == null? 0: TreeDepth(root.right);
System.out.println("leftDepth:" + leftDepth+" rightDepth: "+rightDepth) ;
System.out.println((((leftDepth - rightDepth)*(leftDepth - rightDepth)) < 2));
return (((leftDepth - rightDepth)*(leftDepth - rightDepth)) < 2);
}
// 树的深度
public int TreeDepth(TreeNode root) {
getTreeDepth(root, 0);
return count;
}
// 获取树的深度 先序遍历二叉树
private void getTreeDepth(TreeNode root, int depth) {
count = Math.max(depth,count);
if (root.left != null) {
getTreeDepth(root.left, depth + 1);
}
if (root.right != null) {
getTreeDepth(root.right, depth + 1);
}
}
// 二叉查找树的第k大节点 中序遍历第k 个节点
TreeNode KthNode(TreeNode pRoot, int k)
{
if(k ==0) return null;
int count = 0;
if (pRoot != null) {
Stack<TreeNode> stack = new Stack();
while (pRoot!=null || !stack.empty()) {
if(pRoot!=null){
stack.push(pRoot);
pRoot = pRoot.left;
}else{
TreeNode node = stack.pop();
System.out.println(node.val+"-->");
count++;
if(count == k){
return node;
}
pRoot = node.right;
}
}
}
return null;
}
public static void main(String[] args) {
// 测试 序列是否为后序遍历 二叉树序列
int[] seq = {4, 8, 6, 12, 16, 14, 10};
int[] seq2 = {4, 6, 7, 5};
int[] seq3 = {5};
TreeSolution ts = new TreeSolution();
TreeChildSolution solution = new TreeChildSolution();
// System.out.println(solution.VerifySquenceOfBST(seq3));
System.out.println(solution.IsBalanced_Solution(ts.initBinaryTree2()));
}
}