Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 3d11dd0

Browse filesBrowse files
codinglincodinglin
committed
刷题
1 parent 870530b commit 3d11dd0
Copy full SHA for 3d11dd0

File tree

Expand file treeCollapse file tree

5 files changed

+434
-0
lines changed
Open diff view settings
Filter options
Expand file treeCollapse file tree

5 files changed

+434
-0
lines changed
Open diff view settings
Collapse file

‎src/JZOffer2/Main26.java‎

Copy file name to clipboard
+51Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package JZOffer2;
2+
3+
import java.util.LinkedList;
4+
import java.util.List;
5+
6+
/**
7+
* 树的子结构
8+
* 1.先序遍历树A中的每个节点n_A：对应函数 isSubStructure(A, B)
9+
* 2.判断树A中以n_A为根节点的子树是否包含树B：对应函数 helper(root1, root2)
10+
*
11+
* helper(A, B) 函数：
12+
* 终止条件：
13+
* 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true；
14+
* 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false；
15+
* 当节点 A 和 B 的值不同：说明匹配失败，返回 false；
16+
* 返回值：
17+
* 判断 A 和 B 的左子节点是否相等，即 helper(A.left, B.left) ；
18+
* 判断 A 和 B 的右子节点是否相等，即 helper(A.right, B.right) ；
19+
* isSubStructure(A, B) 函数：
20+
*
21+
* 特例处理：当树 A 为空或树 B 为空时，直接返回 false ；
22+
* 返回值：若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
23+
* 以节点 A 为根节点的子树包含树 B，对应 helper(A, B)；
24+
* 树 B 是 树 A 左子树的子结构，对应 isSubStructure(A.left, B)；
25+
* 树 B 是 树 A 右子树的子结构，对应 isSubStructure(A.right, B)；
26+
*/
27+
public class Main26 {
28+
public boolean isSubStructure(TreeNode A, TreeNode B) {
29+
if(A == null || B == null){
30+
return false;
31+
}
32+
if(A.val == B.val && (helper(A.left, B.left) && helper(A.right, B.right))){
33+
return true;
34+
}
35+
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
36+
}
37+
38+
private boolean helper(TreeNode root1, TreeNode root2) {
39+
if(root2 == null){
40+
return true;
41+
}
42+
if(root1 == null){
43+
return false;
44+
}
45+
if(root1.val == root2.val){
46+
return helper(root1.left, root2.left) && helper(root1.right, root2.right);
47+
}else{
48+
return false;
49+
}
50+
}
51+
}
Collapse file

‎src/featuredTop/LeetCode7.java‎

Copy file name to clipboard
+21Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package featuredTop;
2+
3+
public class LeetCode7 {
4+
public int reverse(int x) {
5+
int res = 0;
6+
while (x != 0){
7+
int temp = x % 10;
8+
//判断是否 大于 最大32位整数
9+
if (res>214748364 || (res==214748364 && temp>7)) {
10+
return 0;
11+
}
12+
//判断是否 小于 最小32位整数
13+
if (res<-214748364 || (res==-214748364 && temp<-8)) {
14+
return 0;
15+
}
16+
res = res * 10 + temp;
17+
x = x / 10;
18+
}
19+
return res;
20+
}
21+
}
Collapse file

‎src/tree/BinaryTree.java‎

Copy file name to clipboard
+273Lines changed: 273 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,273 @@
1+
package tree;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
public class BinaryTree<E> {
9+
/**
10+
* 根结点
11+
*/
12+
private TreeNode<E> root = null;
13+
14+
/**
15+
* 建立二叉树时，用于缓存数据的栈空间
16+
*/
17+
private LinkedList<E> stack = null;
18+
19+
/**
20+
* 保存二叉树数据的列表
21+
*/
22+
private List<E> elements = new ArrayList<>();
23+
24+
/**
25+
* 无参构造方法
26+
*/
27+
public BinaryTree(){
28+
}
29+
30+
/**
31+
* 有参构造方法，默认左递归建立二叉树，
32+
* 因此需要传入左递归顺序的数据
33+
* @param data 左递归顺序的数组数据
34+
*/
35+
public BinaryTree(E[] data){
36+
this.stack = new LinkedList<E>(Arrays.asList(data));
37+
CreateBinaryTree();
38+
}
39+
40+
/**
41+
* 获取根结点
42+
* @return root 返回根结点
43+
*/
44+
public TreeNode<E> getRoot(){
45+
return this.root;
46+
}
47+
48+
/**
49+
* 设置根结点
50+
* @param root 根结点
51+
*/
52+
public void setRoot(TreeNode<E> root){
53+
this.root = root;
54+
}
55+
56+
/**
57+
* 左递归建立二叉树
58+
* @return
59+
*/
60+
private void CreateBinaryTree(){
61+
if(!stack.isEmpty()){
62+
this.root = recursiveCreateBinaryTree(root, stack);
63+
}else{
64+
this.root = null;
65+
}
66+
}
67+
68+
/***
69+
* 左递归建立二叉树，需要传入左递归顺序的二叉树数据
70+
* @param data
71+
*/
72+
public void recursiveCreateBinaryTree(E[] data){
73+
this.stack = new LinkedList<E>(Arrays.asList(data));
74+
if(!stack.isEmpty()){
75+
this.root = recursiveCreateBinaryTree(this.root, this.stack);
76+
}else{
77+
this.root = null;
78+
}
79+
}
80+
/**
81+
* 左递归建立二叉树, 核心算法
82+
* @param node
83+
* @param stack
84+
* @return 返回根节点
85+
*/
86+
private TreeNode<E> recursiveCreateBinaryTree(TreeNode<E> node, LinkedList<E> stack){
87+
if(!stack.isEmpty()){
88+
E value = stack.pop();
89+
if(value == null){
90+
node = null;
91+
}else{
92+
node = new TreeNode<>();
93+
node.val = value;
94+
node.left = recursiveCreateBinaryTree(node.left, stack);
95+
node.right = recursiveCreateBinaryTree(node.right, stack);
96+
}
97+
}else{
98+
return null;
99+
}
100+
return node;
101+
}
102+
103+
104+
/**
105+
* 层序建立二叉树，需要传入层序建立的二叉树数据
106+
* @param data 缓存数据的数组
107+
* @return
108+
*/
109+
public void SequenceCreateBinaryTree(E[] data){
110+
this.stack = new LinkedList<E>(Arrays.asList(data));
111+
if(!stack.isEmpty()){
112+
root = SequenceCreateBinaryTree(root, stack);
113+
}else{
114+
root = new TreeNode<E>();
115+
}
116+
}
117+
118+
/**
119+
* 层序建立二叉树，核心算法
120+
* @param rootNode 根节点
121+
* @return 返回根结点
122+
*/
123+
private TreeNode<E> SequenceCreateBinaryTree(TreeNode<E> rootNode, LinkedList<E> stack){
124+
LinkedList<TreeNode> queue = new LinkedList<>();
125+
if(!stack.isEmpty()){
126+
rootNode = new TreeNode<>();
127+
rootNode.val = stack.pop();
128+
queue.addFirst(rootNode);
129+
}else{
130+
return null;
131+
}
132+
133+
while (!stack.isEmpty()){
134+
TreeNode currentNode = queue.removeLast();
135+
E leftValue = stack.pop();
136+
TreeNode<E> leftNode = null;
137+
if(leftValue != null){
138+
leftNode = new TreeNode<>();
139+
leftNode.val = leftValue;
140+
queue.addFirst(leftNode);
141+
}
142+
currentNode.left = leftNode;
143+
E rightValue = stack.pop();
144+
TreeNode<E> rightNode = null;
145+
if(rightValue != null){
146+
rightNode = new TreeNode<>();
147+
rightNode.val = rightValue;
148+
queue.addFirst(rightNode);
149+
}
150+
currentNode.right = rightNode;
151+
}
152+
return rootNode;
153+
}
154+
155+
156+
/**
157+
* 先序遍历
158+
*/
159+
public void preorder(){
160+
System.out.print("先序遍历：");
161+
this.preorder(root);
162+
}
163+
164+
/**
165+
* 先序遍历
166+
* @param node
167+
*/
168+
private void preorder(TreeNode<E> node){
169+
if(node == null){
170+
return;
171+
}
172+
System.out.print(node.val+" ");
173+
this.preorder(node.left);
174+
this.preorder(node.right);
175+
}
176+
177+
/**
178+
* 后序遍历
179+
*/
180+
public void postorder(){
181+
System.out.print("后序遍历：");
182+
this.postorder(root);
183+
}
184+
185+
/**
186+
* 后序遍历
187+
* @param node
188+
*/
189+
private void postorder(TreeNode<E> node){
190+
if(node == null){
191+
return;
192+
}
193+
this.postorder(node.right);
194+
this.postorder(node.left);
195+
System.out.print(node.val + " ");
196+
}
197+
198+
/**
199+
* 中序遍历
200+
*/
201+
public void inorder(){
202+
System.out.print("中序遍历：");
203+
this.inorder(this.root);
204+
}
205+
206+
/**
207+
* 中序遍历
208+
* @param node
209+
*/
210+
private void inorder(TreeNode<E> node){
211+
if(node == null){
212+
return;
213+
}
214+
this.inorder(node.left);
215+
System.out.print(node.val + " ");
216+
this.inorder(node.right);
217+
}
218+
219+
/**
220+
* 获取二叉树数据元素
221+
* @return List 返回具有二叉树数据元素的列表
222+
*/
223+
public List<E> getElements(){
224+
getElementList(root);
225+
return elements;
226+
}
227+
228+
/**
229+
* 采用先序遍历的方式，获取二叉树数据元素
230+
* @param root 返回以左递归顺序的二叉树数据元素
231+
*/
232+
private void getElementList(TreeNode<E> root){
233+
if(root == null){
234+
this.elements.add(null);
235+
return;
236+
}
237+
this.elements.add(root.val);
238+
getElementList(root.left);
239+
getElementList(root.right);
240+
}
241+
242+
243+
/**
244+
* 获取二叉树的最大深度
245+
* @return 二叉树深度
246+
*/
247+
public int maxDepth(){
248+
return maxDepth(this.root);
249+
}
250+
251+
/***
252+
* 获取该二叉树的深度
253+
* @param root
254+
* @return 返回二叉树深度
255+
*/
256+
private int maxDepth(TreeNode root) {
257+
// 如果到达叶子节点返回0；
258+
if(root == null) {return 0;}
259+
// 左递归查找左子树深度
260+
int left = maxDepth(root.left);
261+
// 右递归查找右子树深度
262+
int right = maxDepth(root.right);
263+
// 返回最大深度并加1
264+
return Math.max(left, right) + 1;
265+
}
266+
267+
@Override
268+
public String toString() {
269+
return "BinaryTree{" +
270+
"root=" + root +
271+
'}';
272+
}
273+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.