Skip to content

Commit 9c0d8e9

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#429 from jinfangzhang/master
081-Week 02
2 parents 6f1bb27 + 8ce6b5e commit 9c0d8e9

11 files changed

+207
-0
lines changed

‎Week 02/id_081/BinaryTreeInorderTraversal.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
import java.util.ArrayList;
2+
import java.util.List;
3+
import java.util.Stack;
4+
5+
/**
6+
* BinaryTreeInorderTraversal
7+
*/
8+
public class BinaryTreeInorderTraversal {
9+
public List<Integer> inorderTraversal(TreeNode root) {
10+
List<Integer> list = new ArrayList()<>();
11+
Stack<TreeNode> stack = new Stack()<>();
12+
TreeNode cur = root;
13+
while(cur!=null || !stack.isEmpty()){
14+
if(cur != null){
15+
stack.push(cur);
16+
cur = cur.left;
17+
}else{
18+
TreeNode node = stack.pop();
19+
list.add(node.val);
20+
cur = node.right;
21+
}
22+
}
23+
return list;
24+
}
25+
}

‎Week 02/id_081/BinaryTreePreorderTraversa.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
/**
2+
* BinaryTreePreorderTraversa
3+
*/
4+
public class BinaryTreePreorderTraversa {
5+
public List<Integer> preorderTraversal(TreeNode root) {
6+
List<Integer> list = new ArrayList<>();
7+
Stack<TreeNode> stack = new Stack<>();
8+
TreeNode cur = root;
9+
while(cur != null || !stack.isEmpty())
10+
if(cur != null){
11+
list.add(cur.val);
12+
stack.push(cur);
13+
cur = cur.left;
14+
}else
15+
cur = stack.pop().right;
16+
return list;
17+
}
18+
19+
}

‎Week 02/id_081/Combinations.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
* Combinations
3+
*/
4+
public class Combinations {
5+
List<List<Integer>> result = new ArrayList<>();
6+
7+
public List<List<Integer>> combine(int n, int k) {
8+
_combine(1, new ArrayList<>(), n, k);
9+
return result;
10+
}
11+
12+
public void _combine(int first, List<Integer> target, int n, int k){
13+
if(k == target.size()){
14+
result.add(new ArrayList<>(target));
15+
return ;
16+
}
17+
18+
for(int i = first; i <= n; i++){
19+
target.add(i);
20+
_combine(i + 1, target, n, k);
21+
target.remove(target.size() - 1);
22+
}
23+
}
24+
}

‎Week 02/id_081/ConstructBinaryTreeFromPreorderAndInorderTraversal.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/**
2+
* ConstructBinaryTreeFromPreorderAndInorderTraversal
3+
*/
4+
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
5+
6+
public TreeNode buildTree(int[] preorder, int[] inorder) {
7+
return _buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
8+
}
9+
10+
public TreeNode _buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight){
11+
if(preLeft > preRight && inLeft > inRight) return null;
12+
13+
int rootValue = preorder[preLeft];
14+
int rootIndex = inLeft;
15+
while(rootValue != inorder[rootIndex]) rootIndex++;
16+
int leftNodeCount = rootIndex - inLeft;
17+
18+
TreeNode leftNode = _buildTree(preorder, preLeft + 1, preLeft + leftNodeCount, inorder, inLeft, rootIndex - 1);
19+
TreeNode rightNode = _buildTree(preorder, preLeft + leftNodeCount + 1, preRight, inorder, rootIndex + 1, inRight);
20+
21+
TreeNode root = new TreeNode(rootValue);
22+
root.left = leftNode;
23+
root.right = rightNode;
24+
return root;
25+
}
26+
}

‎Week 02/id_081/GroupAnagrams.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
/**
2+
* GroupAnagrams
3+
*/
4+
public class GroupAnagrams {
5+
public List<List<String>> groupAnagrams(String[] strs) {
6+
if (strs.length == 0) return new ArrayList();
7+
Map<String, List> ans = new HashMap<String, List>();
8+
for (String s : strs) {
9+
char[] ca = s.toCharArray();
10+
Arrays.sort(ca);
11+
String key = String.valueOf(ca);
12+
if (!ans.containsKey(key)) ans.put(key, new ArrayList());
13+
ans.get(key).add(s);
14+
}
15+
return new ArrayList(ans.values());
16+
}
17+
}

‎Week 02/id_081/LowestCommonAncestorOfABinaryTree.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
/**
2+
* LowestCommonAncestorOfABinaryTree
3+
*/
4+
public class LowestCommonAncestorOfABinaryTree {
5+
6+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
7+
if(root == null || root == p || root == q) return root;
8+
TreeNode left = lowestCommonAncestor(root.left, p, q);
9+
TreeNode right = lowestCommonAncestor(root.right, p, q);
10+
return left == null ? right : right == null ? left : root;
11+
}
12+
}

‎Week 02/id_081/NAryTreeLevelOrderTraversal.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
/**
2+
* NAryTreeLevelOrderTraversal
3+
*/
4+
public class NAryTreeLevelOrderTraversal {
5+
6+
public List<List<Integer>> levelOrder(Node root) {
7+
List<List<Integer>> list = new ArrayList<>();
8+
if(root == null)
9+
return list;
10+
11+
Queue<Node> queue = new LinkedList<>();
12+
queue.add(root);
13+
14+
while (!queue.isEmpty()){
15+
List<Integer> curLevel = new ArrayList<>();
16+
int count = queue.size();
17+
for(int i = 0; i < count; i++){
18+
Node node = queue.poll();
19+
curLevel.add(node.val);
20+
for(Node n : node.children)
21+
queue.add(n);
22+
}
23+
list.add(curLevel);
24+
}
25+
return list;
26+
}
27+
}

‎Week 02/id_081/NAryTreePostorderTraversal.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* NAryTreePostorderTraversal
3+
*/
4+
public class NAryTreePostorderTraversal {
5+
public List<Integer> postorder(Node root) {
6+
List<Integer> list = new ArrayList<>();
7+
realWork(root, list);
8+
return list;
9+
}
10+
11+
public void realWork(Node root, List<Integer> list){
12+
if (root == null)
13+
return ;
14+
for(Node node : root.children)
15+
realWork(node, list);
16+
list.add(root.val);
17+
}
18+
}

‎Week 02/id_081/NOTE.md‎

100644100755
File mode changed.

‎Week 02/id_081/TwoSum.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
/**
2+
* TwoSum
3+
*/
4+
public class TwoSum {
5+
6+
public int[] twoSum(int[] nums, int target) {
7+
Map<Integer, Integer> map = new HashMap<>();
8+
for(int i = 0; i < nums.length; i++){
9+
int complement = target - nums[i];
10+
if(!map.containsKey(complement)) map.put(nums[i], i);
11+
else return new int[]{i, map.get(complement)};
12+
}
13+
return new int[]{};
14+
}
15+
}

0 commit comments

Comments
 (0)