Skip to content

Commit 796b893

Browse files
kunkunthreekunkunthree
committed
完成所有leetcode上的easy和medium难度的题
1 parent 32315e9 commit 796b893

226 files changed

Lines changed: 15605 additions & 9 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎ChapterAlgorithm/src/algorithm/leetcode/algorithm/Interval.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,4 +11,8 @@ public Interval(int s,int e) {
1111
start = s;
1212
end = e;
1313
}
14+
@Override
15+
public String toString() {
16+
return "[" + start + "," + end +"]";
17+
}
1418
}

‎ChapterAlgorithm/src/algorithm/leetcode/algorithm/MakeTitleToClassName.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,12 @@ public static void main(String[] args) {
1010
String s;
1111
while(in.hasNext()){
1212
s = in.nextLine();
13+
if(s == null || s.length() == 0)continue;
1314
System.out.println(getClassName(s));
1415
}
1516
}
1617
public static String getClassName(String s){
17-
String[] str = s.split(" ");
18+
String[] str = s.trim().split(" ");
1819
StringBuilder result = new StringBuilder("NO");
1920
// System.out.println(Arrays.toString(str[0].split("\\.")));
2021
str[0] = str[0].split("\\.")[0];

‎ChapterAlgorithm/src/algorithm/leetcode/algorithm/NO102_BinaryTreeLevelOrderTraversal.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package algorithm.leetcode.algorithm;
2+
/*
3+
* medium
4+
* 102. Binary Tree Level Order Traversal
5+
* Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
6+
7+
For example:
8+
Given binary tree [3,9,20,null,null,15,7],
9+
10+
3
11+
/ \
12+
9 20
13+
/ \
14+
15 7
15+
16+
return its level order traversal as:
17+
18+
[
19+
[3],
20+
[9,20],
21+
[15,7]
22+
]
23+
24+
*/
25+
import java.util.*;
26+
public class NO102_BinaryTreeLevelOrderTraversal {
27+
//方法1：
28+
//利用queue分层遍历二叉树
29+
public List<List<Integer>> levelOrder(TreeNode root) {
30+
Queue<TreeNode> queue = new LinkedList<TreeNode>();
31+
List<List<Integer>> ll = new ArrayList<List<Integer>>();
32+
if(root == null){
33+
return ll;
34+
}
35+
List<Integer> l;
36+
queue.offer(root);
37+
TreeNode node;
38+
while(!queue.isEmpty()){
39+
l = new ArrayList<Integer>();
40+
int length = queue.size();
41+
for(int i = 0 ; i < length ; i++){
42+
node = queue.poll();
43+
l.add(node.val);
44+
if(node.left != null){
45+
queue.offer(node.left);
46+
}
47+
if(node.right != null){
48+
queue.offer(node.right);
49+
}
50+
}
51+
ll.add(l);
52+
}
53+
return ll;
54+
}
55+
56+
//方法2：
57+
//BFS，通过深度优先搜索，得到每层的节点，并将其添加到对应层的数组中
58+
public List<List<Integer>> levelOrder2(TreeNode root) {
59+
List<List<Integer>> ll = new ArrayList<List<Integer>>();
60+
levelOrderHelper(ll,root,0);
61+
return ll;
62+
}
63+
public void levelOrderHelper(List<List<Integer>> ll,TreeNode node,int height){
64+
if(node == null){
65+
return;
66+
}
67+
List<Integer> l;
68+
if(ll.size() <= height){
69+
l = new ArrayList<Integer>();
70+
ll.add(l);
71+
}else{
72+
l = ll.get(height);
73+
}
74+
l.add(node.val);
75+
levelOrderHelper(ll,node.left,height+1);
76+
levelOrderHelper(ll,node.right,height+1);
77+
}
78+
}

‎ChapterAlgorithm/src/algorithm/leetcode/algorithm/NO103_BinaryTreeZigzagLevelOrderTraversal.java‎

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
package algorithm.leetcode.algorithm;
2+
/*
3+
* medium
4+
* 103. Binary Tree Zigzag Level Order Traversal
5+
* Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
6+
7+
For example:
8+
Given binary tree [3,9,20,null,null,15,7],
9+
10+
3
11+
/ \
12+
9 20
13+
/ \
14+
15 7
15+
16+
return its zigzag level order traversal as:
17+
18+
[
19+
[3],
20+
[20,9],
21+
[15,7]
22+
]
23+
24+
*/
25+
import java.util.*;
26+
public class NO103_BinaryTreeZigzagLevelOrderTraversal {
27+
public static void main(String[] args) {
28+
Stack<Integer> stack = new Stack<Integer>();
29+
stack.push(1);
30+
stack.push(2);
31+
stack.push(3);
32+
System.out.println(stack.pop());
33+
Queue<Integer> queue = new LinkedList<Integer>();
34+
boolean order = false;
35+
System.out.println(order);
36+
order^=true;
37+
System.out.println(order);
38+
}
39+
//方法1：
40+
//用两个栈来分别存储从左到右和从右到左的子节点
41+
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
42+
List<List<Integer>> ll = new ArrayList<List<Integer>>();
43+
Stack<TreeNode> stack1 = new Stack<TreeNode>();
44+
Stack<TreeNode> stack2 = new Stack<TreeNode>();
45+
if(root == null){
46+
return ll;
47+
}
48+
List<Integer> l;
49+
stack1.push(root);
50+
int length;
51+
TreeNode node;
52+
while(!stack1.isEmpty()){
53+
l = new ArrayList<Integer>();
54+
length = stack1.size();
55+
while(!stack1.isEmpty()){
56+
node = stack1.pop();
57+
l.add(node.val);
58+
if(node.left != null){
59+
stack2.push(node.left);
60+
}
61+
if(node.right != null){
62+
stack2.push(node.right);
63+
}
64+
}
65+
ll.add(l);
66+
if(!stack2.isEmpty()){
67+
l = new ArrayList<Integer>();
68+
length = stack2.size();
69+
while(!stack2.isEmpty()){
70+
node = stack2.pop();
71+
l.add(node.val);
72+
if(node.right != null){
73+
stack1.push(node.right);
74+
}
75+
if(node.left != null){
76+
stack1.push(node.left);
77+
}
78+
}
79+
ll.add(l);
80+
}
81+
}
82+
return ll;
83+
}
84+
//方法2：
85+
//和分层顺序扫描一样，只是list添加方法的参数不一样，从左到右时，直接add(val)，从右到左时，调用add(0,val)
86+
//用一个boolean型变量表示方向
87+
public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
88+
List<List<Integer>> ll = new ArrayList<List<Integer>>();
89+
Queue<TreeNode> queue = new LinkedList<TreeNode>();
90+
if(root == null){
91+
return ll;
92+
}
93+
List<Integer> l;
94+
queue.offer(root);
95+
int length;
96+
TreeNode node;
97+
boolean order = false; //false表示从右到左，true表示从左到右
98+
while(!queue.isEmpty()){
99+
l = new ArrayList<Integer>();
100+
length = queue.size();
101+
for(int i = 0 ; i < length ; i++){
102+
node = queue.poll();
103+
if(order){
104+
l.add(0,node.val);
105+
}else{
106+
l.add(node.val);
107+
}
108+
if(node.left != null){
109+
queue.offer(node.left);
110+
}
111+
if(node.right != null){
112+
queue.offer(node.right);
113+
}
114+
}
115+
order^=true;
116+
ll.add(l);
117+
}
118+
return ll;
119+
}
120+
121+
//方法3：
122+
//DFS，通过高度的奇偶性，当为偶数时调用add(val)，当为偶数时调用add(0,val)
123+
public List<List<Integer>> zigzagLevelOrder3(TreeNode root) {
124+
List<List<Integer>> ll = new ArrayList<List<Integer>>();
125+
zigzagLevelOrderHelper(ll,root,0);
126+
return ll;
127+
128+
}
129+
public void zigzagLevelOrderHelper(List<List<Integer>> ll,TreeNode root,int height){
130+
if(root == null){
131+
return;
132+
}
133+
List<Integer> l;
134+
if(ll.size() <= height){
135+
l = new ArrayList<Integer>();
136+
ll.add(l);
137+
}else{
138+
l = ll.get(height);
139+
}
140+
if((height&1) == 1){
141+
l.add(0,root.val);
142+
}else{
143+
l.add(root.val);
144+
}
145+
zigzagLevelOrderHelper(ll,root.left,height+1);
146+
zigzagLevelOrderHelper(ll,root.right,height+1);
147+
}
148+
}

‎ChapterAlgorithm/src/algorithm/leetcode/algorithm/NO105_ConstructBinaryTreefromPreorderandInorderTraversal.java‎

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
package algorithm.leetcode.algorithm;
2+
/*
3+
* medium
4+
* 105. Construct Binary Tree from Preorder and Inorder Traversal
5+
* Given preorder and inorder traversal of a tree, construct the binary tree.
6+
7+
Note:
8+
You may assume that duplicates do not exist in the tree.
9+
*/
10+
import java.util.*;
11+
public class NO105_ConstructBinaryTreefromPreorderandInorderTraversal {
12+
public static void main(String[] args) {
13+
int[] preorder = new int[]{1,2,4,5,3,6,7};
14+
int[] inorder = new int[]{4,2,5,1,6,3,7};
15+
System.out.println(buildTree3(preorder, inorder));
16+
}
17+
public static TreeNode buildTree(int[] preorder, int[] inorder) {
18+
return buildTree(preorder,0,inorder,0,preorder.length);
19+
}
20+
public static TreeNode buildTree(int[] preorder,int preIndex, int[] inorder,int inIndex,int length) {
21+
//检查边界条件
22+
if(preIndex < 0 || inIndex < 0
23+
|| preIndex >= preorder.length || inIndex >= inorder.length
24+
|| length == 0){
25+
return null;
26+
}
27+
//先序遍历的第一个节点为根
28+
TreeNode node = new TreeNode(preorder[preIndex]);
29+
node.left = null;
30+
node.right = null;
31+
//叶子节点则返回
32+
if(length == 1){
33+
return node;
34+
}
35+
int tmpLength = 0;
36+
int leftEndIndex = inIndex;
37+
//计算左子树长度
38+
while(inorder[leftEndIndex] != preorder[preIndex]){
39+
tmpLength++;
40+
if(tmpLength > length){
41+
break;
42+
}
43+
leftEndIndex++;
44+
}
45+
//左子树长度
46+
int nLeftLength = tmpLength;
47+
//右子树长度
48+
int nRightLength = length - tmpLength - 1;
49+
//重建左子树
50+
node.left = buildTree(preorder,preIndex+1,inorder,inIndex,nLeftLength);
51+
//重建右子树
52+
node.right = buildTree(preorder,preIndex+nLeftLength+1,inorder,leftEndIndex+1,nRightLength);
53+
return node;
54+
}
55+
56+
//递归简洁写法
57+
public TreeNode buildTree2(int[] preorder, int[] inorder) {
58+
return helper(0, 0, inorder.length - 1, preorder, inorder);
59+
}
60+
61+
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
62+
if (preStart > preorder.length - 1 || inStart > inEnd) {
63+
return null;
64+
}
65+
TreeNode root = new TreeNode(preorder[preStart]);
66+
int inIndex = 0; // Index of current root in inorder
67+
for (int i = inStart; i <= inEnd; i++) {
68+
if (inorder[i] == root.val) {
69+
inIndex = i;
70+
}
71+
}
72+
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
73+
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
74+
return root;
75+
}
76+
77+
public static TreeNode buildTree3(int[] preorder, int[] inorder) {
78+
if(preorder == null || preorder.length == 0){
79+
return null;
80+
}
81+
Stack<TreeNode> StackNode =new Stack<TreeNode>();
82+
Stack<Integer> stackInt = new Stack<Integer>();
83+
TreeNode t,r,root;
84+
85+
int i = 0,j = 0,f = 0;
86+
// stackInt.push(preorder[i]);
87+
root = new TreeNode(preorder[i]);
88+
StackNode.push(root);
89+
t = root;
90+
i++;
91+
while(i<preorder.length)
92+
{
93+
if(!StackNode.isEmpty() && StackNode.peek().val==inorder[j])
94+
{
95+
t = StackNode.pop();
96+
// stackInt.pop();
97+
f = 1;
98+
j++;
99+
}
100+
else
101+
{
102+
if(f==0)
103+
{
104+
// stackInt.push(preorder[i]);
105+
t.left = new TreeNode(preorder[i]);
106+
t = t.left;
107+
StackNode.push(t);
108+
i++;
109+
}
110+
else
111+
{
112+
f = 0;
113+
// stackInt.push(preorder[i]);
114+
t.right = new TreeNode(preorder[i]);
115+
t = t.right;
116+
StackNode.push(t);
117+
i++;
118+
}
119+
}
120+
}
121+
122+
return root;
123+
}
124+
}

0 commit comments

Comments
 (0)