Skip to content

Commit a0130d7

Browse files
fishercoder1534fishercoder1534
committed
add 1367
1 parent 51b29a6 commit a0130d7

File tree

3 files changed

+137
-0
lines changed

3 files changed

+137
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★
88

99
| # | Title | Solutions | Video | Difficulty | Tag
1010
|-----|----------------|---------------|--------|-------------|-------------
11+
|1367|[Linked List in Binary Tree](https://leetcode.com/problems/linked-list-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1367.java) | |Medium||DP, Linked List, Tree
1112
|1362|[Closest Divisors](https://leetcode.com/problems/closest-divisors/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1362.java) | |Medium||Math
1213
|1361|[Validate Binary Tree Nodes](https://leetcode.com/problems/validate-binary-tree-nodes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1361.java) | |Medium||Graph
1314
|1360|[Number of Days Between Two Dates](https://leetcode.com/problems/number-of-days-between-two-dates/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1360.java) | |Easy||

‎src/main/java/com/fishercoder/solutions/_1367.java

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.ListNode;
4+
import com.fishercoder.common.classes.TreeNode;
5+
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
9+
/**
10+
* 1367. Linked List in Binary Tree
11+
*
12+
* Given a binary tree root and a linked list with head as the first node.
13+
* Return True if all the elements in the linked list starting from the head correspond to some downward path
14+
* connected in the binary tree otherwise return False.
15+
* In this context downward path means a path that starts at some node and goes downwards.
16+
*
17+
* Example 1:
18+
* Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
19+
* Output: true
20+
* Explanation: Nodes in blue form a subpath in the binary Tree.
21+
*
22+
* Example 2:
23+
* Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
24+
* Output: true
25+
*
26+
* Example 3:
27+
* Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
28+
* Output: false
29+
* Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.
30+
*
31+
* Constraints:
32+
* 1 <= node.val <= 100 for each node in the linked list and binary tree.
33+
* The given linked list will contain between 1 and 100 nodes.
34+
* The given binary tree will contain between 1 and 2500 nodes.
35+
* */
36+
public class _1367 {
37+
public static class Solution1 {
38+
List<List<Integer>> paths = new ArrayList<>();
39+
40+
public boolean isSubPath(ListNode head, TreeNode root) {
41+
List<Integer> list = getList(head);
42+
findAllPaths(root, new ArrayList<>());
43+
for (List<Integer> path : paths) {
44+
if (path.size() >= list.size()) {
45+
if (find(list, path)) {
46+
return true;
47+
}
48+
}
49+
}
50+
return false;
51+
}
52+
53+
private boolean find(List<Integer> list, List<Integer> path) {
54+
int i = 0;
55+
int j = 0;
56+
for (; i <= path.size() - list.size(); i++) {
57+
j = 0;
58+
int tmpI = i;
59+
while (j < list.size() && tmpI < path.size() && list.get(j) == path.get(tmpI)) {
60+
tmpI++;
61+
j++;
62+
}
63+
if (j >= list.size()) {
64+
return true;
65+
}
66+
}
67+
return j >= list.size();
68+
}
69+
70+
private void findAllPaths(TreeNode root, List<Integer> path) {
71+
if (root == null) {
72+
return;
73+
}
74+
path.add(root.val);
75+
if (root.left == null && root.right == null) {
76+
paths.add(new ArrayList<>(path));
77+
path.remove(path.size() - 1);
78+
return;
79+
}
80+
findAllPaths(root.left, path);
81+
findAllPaths(root.right, path);
82+
path.remove(path.size() - 1);
83+
}
84+
85+
private List<Integer> getList(ListNode head) {
86+
List<Integer> list = new ArrayList<>();
87+
while (head != null) {
88+
list.add(head.val);
89+
head = head.next;
90+
}
91+
return list;
92+
}
93+
}
94+
}

‎src/test/java/com/fishercoder/_1367Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.ListNode;
4+
import com.fishercoder.common.classes.TreeNode;
5+
import com.fishercoder.common.utils.LinkedListUtils;
6+
import com.fishercoder.common.utils.TreeUtils;
7+
import com.fishercoder.solutions._1367;
8+
import org.junit.BeforeClass;
9+
import org.junit.Test;
10+
11+
import java.util.Arrays;
12+
13+
import static org.junit.Assert.assertEquals;
14+
15+
public class _1367Test {
16+
private static _1367.Solution1 solution1;
17+
18+
@Test
19+
public void test1() {
20+
solution1 = new _1367.Solution1();
21+
ListNode head = LinkedListUtils.contructLinkedList(new int[]{4, 2, 8});
22+
TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, 4, 4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3));
23+
assertEquals(true, solution1.isSubPath(head, root));
24+
}
25+
26+
@Test
27+
public void test2() {
28+
solution1 = new _1367.Solution1();
29+
ListNode head = LinkedListUtils.contructLinkedList(new int[]{1, 4, 2, 6});
30+
TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, 4, 4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3));
31+
assertEquals(true, solution1.isSubPath(head, root));
32+
}
33+
34+
@Test
35+
public void test3() {
36+
solution1 = new _1367.Solution1();
37+
ListNode head = LinkedListUtils.contructLinkedList(new int[]{1, 4, 2, 6, 8});
38+
TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, 4, 4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3));
39+
assertEquals(false, solution1.isSubPath(head, root));
40+
}
41+
42+
}

0 commit comments

Comments
 (0)