Skip to content

Commit d505d12

Browse files
jsrcjsrc
committed
296-Week 02
1 parent 5e82a3e commit d505d12

6 files changed

Lines changed: 252 additions & 0 deletions

File tree

‎Week 02/id_296/LeetCode_144_296.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/*
2+
* @lc app=leetcode.cn id=144 lang=java
3+
*
4+
* [144] 二叉树的前序遍历
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode(int x) { val = x; }
15+
* }
16+
*/
17+
class Solution {
18+
public List<Integer> preorderTraversal(TreeNode root) {
19+
List<Integer> res = new ArrayList<>();
20+
helper(root, res);
21+
return res;
22+
}
23+
24+
public void helper(TreeNode root, List<Integer> res) {
25+
if (root != null) {
26+
res.add(root.val);
27+
if (root.left != null) {
28+
helper(root.left, res);
29+
}
30+
if (root.right != null) {
31+
helper(root.right, res);
32+
}
33+
}
34+
}
35+
}
36+
// @lc code=end
37+

‎Week 02/id_296/LeetCode_236_296.java‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
/*
2+
* @lc app=leetcode.cn id=236 lang=java
3+
*
4+
* [236] 二叉树的最近公共祖先
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode(int x) { val = x; }
15+
* }
16+
*/
17+
class Solution {
18+
19+
private TreeNode ans;
20+
21+
public Solution() {
22+
// Variable to store LCA node.
23+
this.ans = null;
24+
}
25+
26+
private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
27+
28+
// If reached the end of a branch, return false.
29+
if (currentNode == null) {
30+
return false;
31+
}
32+
33+
// Left Recursion. If left recursion returns true, set left = 1 else 0
34+
int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;
35+
36+
// Right Recursion
37+
int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;
38+
39+
// If the current node is one of p or q
40+
int mid = (currentNode == p || currentNode == q) ? 1 : 0;
41+
42+
// If any two of the flags left, right or mid become True
43+
if (mid + left + right >= 2) {
44+
this.ans = currentNode;
45+
}
46+
47+
// Return true if any one of the three bool values is True.
48+
return (mid + left + right > 0);
49+
}
50+
51+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
52+
// Traverse the tree
53+
this.recurseTree(root, p, q);
54+
return this.ans;
55+
}
56+
}
57+
58+
// @lc code=end
59+

‎Week 02/id_296/LeetCode_49_296.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
* @lc app=leetcode.cn id=49 lang=java
3+
*
4+
* [49] 字母异位词分组
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
public List<List<String>> groupAnagrams(String[] strs) {
10+
HashMap<String, List<String>> hash = new HashMap<>();
11+
for (int i = 0; i < strs.length; i++) {
12+
char[] s_arr = strs[i].toCharArray();
13+
// 排序
14+
Arrays.sort(s_arr);
15+
// 映射到 key
16+
String key = String.valueOf(s_arr);
17+
// 添加到对应的类中
18+
if (hash.containsKey(key)) {
19+
hash.get(key).add(strs[i]);
20+
} else {
21+
List<String> temp = new ArrayList<String>();
22+
temp.add(strs[i]);
23+
hash.put(key, temp);
24+
}
25+
}
26+
return new ArrayList<List<String>>(hash.values());
27+
}
28+
}
29+
// @lc code=end
30+

‎Week 02/id_296/LeetCode_589_296.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/*
2+
* @lc app=leetcode.cn id=589 lang=java
3+
*
4+
* [589] N叉树的前序遍历
5+
*/
6+
7+
// @lc code=start
8+
/*
9+
// Definition for a Node.
10+
class Node {
11+
public int val;
12+
public List<Node> children;
13+
14+
public Node() {}
15+
16+
public Node(int _val,List<Node> _children) {
17+
val = _val;
18+
children = _children;
19+
}
20+
};
21+
*/
22+
class Solution {
23+
List<Integer> res = new ArrayList<Integer>();
24+
25+
public List<Integer> preorder(Node root) {
26+
helper(root);
27+
return res;
28+
}
29+
30+
public void helper(Node root) {
31+
if (root == null) {
32+
return;
33+
}
34+
res.add(root.val);
35+
int s = root.children.size();
36+
for (int i = 0; i < s; i++) {
37+
helper(root.children.get(i));
38+
}
39+
}
40+
41+
}
42+
// @lc code=end
43+

‎Week 02/id_296/LeetCode_590_296.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/*
2+
* @lc app=leetcode.cn id=590 lang=java
3+
*
4+
* [590] N叉树的后序遍历
5+
*/
6+
7+
// @lc code=start
8+
/*
9+
// Definition for a Node.
10+
class Node {
11+
public int val;
12+
public List<Node> children;
13+
14+
public Node() {}
15+
16+
public Node(int _val,List<Node> _children) {
17+
val = _val;
18+
children = _children;
19+
}
20+
};
21+
*/
22+
class Solution {
23+
List<Integer> res = new ArrayList<Integer>();
24+
25+
public List<Integer> postorder(Node root) {
26+
helper(root);
27+
return res;
28+
}
29+
30+
public void helper(Node root) {
31+
if (root == null) {
32+
return;
33+
}
34+
int s = root.children.size();
35+
for (int i = 0; i < s; i++) {
36+
helper(root.children.get(i));
37+
}
38+
res.add(root.val);
39+
}
40+
}
41+
// @lc code=end
42+

‎Week 02/id_296/LeetCode_94_296.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
import java.util.ArrayList;
2+
import java.util.List;
3+
4+
/*
5+
* @lc app=leetcode.cn id=94 lang=java
6+
*
7+
* [94] 二叉树的中序遍历
8+
*/
9+
10+
// @lc code=start
11+
/**
12+
* Definition for a binary tree node.
13+
* public class TreeNode {
14+
* int val;
15+
* TreeNode left;
16+
* TreeNode right;
17+
* TreeNode(int x) { val = x; }
18+
* }
19+
*/
20+
class Solution {
21+
public List<Integer> inorderTraversal(TreeNode root) {
22+
List<Integer> res = new ArrayList<>();
23+
helper(root, res);
24+
return res;
25+
}
26+
//使用辅助类完成中序遍历
27+
//树的常规基础操作之一，必须掌握
28+
public void helper(TreeNode root, List<Integer> res) {
29+
if (root != null) {
30+
if (root.left != null) {
31+
helper(root.left, res);
32+
}
33+
res.add(root.val);
34+
if (root.right != null) {
35+
helper(root.right, res);
36+
}
37+
}
38+
}
39+
}
40+
// @lc code=end
41+

0 commit comments

Comments
 (0)