_1367.java

packagecom.fishercoder.solutions.secondthousand;

importcom.fishercoder.common.classes.ListNode;
importcom.fishercoder.common.classes.TreeNode;
importjava.util.ArrayList;
importjava.util.List;

publicclass_1367 {
publicstaticclassSolution1 {
List<List<Integer>> paths = newArrayList<>();

publicbooleanisSubPath(ListNodehead, TreeNoderoot) {
List<Integer> list = getList(head);
findAllPaths(root, newArrayList<>());
for (List<Integer> path : paths) {
if (path.size() >= list.size()) {
if (find(list, path)) {
returntrue;
 }
 }
 }
returnfalse;
 }

privatebooleanfind(List<Integer> list, List<Integer> path) {
inti = 0;
intj = 0;
for (; i <= path.size() - list.size(); i++) {
j = 0;
inttmpI = i;
while (j < list.size() && tmpI < path.size() && list.get(j) == path.get(tmpI)) {
tmpI++;
j++;
 }
if (j >= list.size()) {
returntrue;
 }
 }
returnj >= list.size();
 }

privatevoidfindAllPaths(TreeNoderoot, List<Integer> path) {
if (root == null) {
return;
 }
path.add(root.val);
if (root.left == null && root.right == null) {
paths.add(newArrayList<>(path));
path.remove(path.size() - 1);
return;
 }
findAllPaths(root.left, path);
findAllPaths(root.right, path);
path.remove(path.size() - 1);
 }

privateList<Integer> getList(ListNodehead) {
List<Integer> list = newArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
 }
returnlist;
 }
 }
}