Skip to content

Commit fe654f0

Browse files
awangdevawangdev
committed
3.1.2016n
1 parent 4fb7e67 commit fe654f0

File tree

6 files changed

+404
-197
lines changed

6 files changed

+404
-197
lines changed

‎Java/Binary Tree Path Sum.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
遍历到底，比较sum vs. target。
55
注意divide的情况。要把遍历的例子写写。
66

7+
LeetCode: Path Sum II
78

89
```
910
/*
@@ -48,6 +49,40 @@
4849
* }
4950
*/
5051

52+
/*
53+
3.1.2016 Recap
54+
Same approach
55+
*/
56+
public class Solution {
57+
public List<List<Integer>> pathSum(TreeNode root, int sum) {
58+
List<List<Integer>> rst = new ArrayList<List<Integer>>();
59+
if (root == null) {
60+
return rst;
61+
}
62+
dfs(rst, new ArrayList<Integer>(), root, 0, sum);
63+
64+
return rst;
65+
}
66+
67+
public void dfs(List<List<Integer>> rst, ArrayList<Integer> list, TreeNode node, int add, int sum) {
68+
list.add(node.val);
69+
if (node.left == null && node.right == null) {
70+
if (add + node.val == sum) {
71+
rst.add(new ArrayList<Integer>(list));
72+
}
73+
return;
74+
}
75+
if (node.left != null) {
76+
dfs(rst, list, node.left, add + node.val, sum);
77+
list.remove(list.size() - 1);
78+
}
79+
if (node.right != null) {
80+
dfs(rst, list, node.right, add + node.val, sum);
81+
list.remove(list.size() - 1);
82+
}
83+
}
84+
}
85+
5186
public class Solution {
5287
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
5388
List<List<Integer>> rst = new ArrayList<List<Integer>>();

‎Java/Populating Next Right Pointers in Each Node.java

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
M
2+
3+
方法1：
4+
题目要求DFS。
5+
其实basic implementation. 每次处理node.left.next = node.right; node.right.next = node.next.left;
6+
7+
8+
方法2:
9+
不和题意，用了queue space，与Input成正比。太大。
10+
11+
BFS over Tree。 用Queue 和 queue.size()，老规矩。
12+
process每层queue时, 注意把next pointer加上去就好.
13+
14+
```
15+
/*
16+
Given a binary tree
17+
18+
struct TreeLinkNode {
19+
TreeLinkNode *left;
20+
TreeLinkNode *right;
21+
TreeLinkNode *next;
22+
}
23+
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
24+
25+
Initially, all next pointers are set to NULL.
26+
27+
Note:
28+
29+
You may only use constant extra space.
30+
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
31+
For example,
32+
Given the following perfect binary tree,
33+
1
34+
/ \
35+
2 3
36+
/ \ / \
37+
4 5 6 7
38+
After calling your function, the tree should look like:
39+
1 -> NULL
40+
/ \
41+
2 -> 3 -> NULL
42+
/ \ / \
43+
4->5->6->7 -> NULL
44+
Hide Tags Tree Depth-first Search
45+
Hide Similar Problems (H) Populating Next Right Pointers in Each Node II (M) Binary Tree Right Side View
46+
47+
*/
48+
49+
50+
/**
51+
* Definition for binary tree with next pointer.
52+
* public class TreeLinkNode {
53+
* int val;
54+
* TreeLinkNode left, right, next;
55+
* TreeLinkNode(int x) { val = x; }
56+
* }
57+
*/
58+
59+
//DFS. Basic implementation according to problem.
60+
public class Solution {
61+
public void connect(TreeLinkNode root) {
62+
if (root == null || (root.left == null && root.right == null)) {
63+
return;
64+
}
65+
root.left.next = root.right;
66+
dfs(root.left);
67+
dfs(root.right);
68+
}
69+
70+
public void dfs(TreeLinkNode node) {
71+
if (node == null || node.left == null || node.right == null) {
72+
return;
73+
}
74+
node.left.next = node.right;
75+
if (node.next != null)
76+
node.right.next = node.next.left;
77+
dfs(node.left);
78+
dfs(node.right);
79+
}
80+
}
81+
82+
83+
84+
85+
//BFS, However, 不和题意。 point each node to the next in queue. if none, add null
86+
public class Solution {
87+
public void connect(TreeLinkNode root) {
88+
if (root == null || (root.left == null && root.right == null)) {
89+
return;
90+
}
91+
Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
92+
queue.offer(root);
93+
int size = 0;
94+
95+
while (!queue.isEmpty()) {
96+
size = queue.size();
97+
for (int i = 0; i < size; i++) {
98+
TreeLinkNode node = queue.poll();
99+
if (i < size - 1) {
100+
node.next = queue.peek();
101+
} else {
102+
node.next = null;
103+
}
104+
if (node.left != null) {
105+
queue.offer(node.left);
106+
}
107+
if (node.right != null) {
108+
queue.offer(node.right);
109+
}
110+
}
111+
size = queue.size();
112+
}
113+
}
114+
}
115+
```

‎Java/Word Pattern.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,10 @@
1+
E
2+
13
每个char代表一个pattern。用HashMap<char, str>.
24
但不够，如果a也match dog, b也match dog, 纠错了。比如pattern = "abba", str = "dog dog dog dog"。
35
因此第二个HashMap<str, char> 反过来。
46
确保pattern和str一一对应。
7+
58
```
69
/*
710
Given a pattern and a string str, find if str follows the same pattern.
@@ -25,6 +28,39 @@ Hide Similar Problems (E) Isomorphic Strings (H) Word Pattern II
2528
2629
*/
2730

31+
/*
32+
3.1.2016 recap.
33+
HashMap, one to one mapping
34+
*/
35+
public class Solution {
36+
public boolean wordPattern(String pattern, String str) {
37+
if (pattern == null || pattern.length() == 0 || str == null || str.length() == 0) {
38+
return false;
39+
}
40+
41+
String[] strArr = str.split(" ");
42+
if (pattern.length() != strArr.length) {
43+
return false;
44+
}
45+
HashMap<Character, String> map = new HashMap<Character, String>();
46+
47+
for (int i = 0; i < pattern.length(); i++) {
48+
char c = pattern.charAt(i);
49+
String s = strArr[i];
50+
if (!map.containsKey(c)) {
51+
if (map.containsValue(s)) {
52+
return false;
53+
}
54+
map.put(c, s);
55+
} else if (!map.get(c).equals(s)) {
56+
return false;
57+
}
58+
}
59+
return true;
60+
}
61+
}
62+
63+
2864
/*
2965
Thoughts:
3066
2 HashMap<char, string>, HashMap<String, char> double check

0 commit comments

Comments
 (0)