given
- 이진 트리와 연결 리스트가 주어짐
when
- 연결 리스트가 이진 트리의 하향 경로로 표현되는지 확인
- 이진 트리의 하향 경로는 임의의 노드에서 시작하여 그 다음 자식 노드로 확장되어 하향하는 경로로 정의됨
then
접근1) DFS
- 직접적으로 DFS(Depth-first-search_를 사용하여 트리의 모든 가능한 경로를 탐색
- 이 방법을 사용하면 다음으로 이동하기 전 각 경로를 완전히 검토 가능
- 우리는 트리의 루트에서 시작하여 그 값을 연결 리스트의 헤드와 비교하고
- 만약 일치하면 트리 노드의 왼쪽과 오른쪽 자식을 연결 리스트의 다음 노드와 비교하여 계쏙
- 트리 노드의 값이 연결 리스트 노드와 일치하지 않으면, 우리는 그 경로가 일치로 이어질 수 없기 때문에 그 경로 탐색을 중단
- 그런 다음 뒤로 돌아가서 다음 가능한 경로를 시도
- root null인 경우 false(기본 케이스)를 반환
- checkPath(root, head) 트리에서 연결 리스트의 경로를 확인하기 위해 호출
- checkPath 기능:
- node null인 경우 false(기본 케이스)를 반환
- dfs(node, head) 일치하는 경로가 node에서 시작하는지 확인하기 위해 호출
- dfs 반환하는 경우 true, true(일치하는 경로가 발견됨)을 반환
- checkPath같은 head로 왼쪽과 오른쪽 서브 트리를 재귀적으로 호출
- dfs 기능
- head null인 경우, true(리스트의 모든 노드가 일치했음)을 반환
- node null인 경우, false(모든 노드와 일치하지 않고 트리의 끝에 도달한 경우)를 반환
- node와 head가 불일치한 경우 false return
- node의 왼쪽 / 오른쪽 자식과 head->next를 dfs로 재귀 호출
- checkPath 또는 dfs가 일치하는 경로를 확인하면 true를 return하고 아니면 checking continue
class Solution { public boolean isSubPath(ListNode head, TreeNode root) { if (root == null) return false; return checkPath(root, head); } private boolean checkPath(TreeNode ndoe, ListNode head) { if (node == null) return false; // mathcing path is found if (dfs(node, head)) return true; return checkPath(node,left head) || checkPath(node.right, head); } private boolean dfs(TreeNode node, ListNode head) { if (head==null) return true; // all nodes in the list matched if (node==null) return false; // reached end of tree without matching all nodes // value mismatch if (node.val != head.val) return false; return dfs(node.left, head.next) || dfs(node.right, head.next); }
복잡도 진단
임의) n = 트리의 노드 수, n = 연결 리스트의 길이
- 시간 복잡도 O(n*m)
최악의 경우, 연결 리스트의 잠재적 시작점으로 트리의 모든 노드를 확인해야 할 수 있음
각 노드에 대해 연결 리스트의 최대 m개 노드를 탐색해야 할 수도 있음
- 공간 복잡도 O(n+m)
솔루션의 재귀적 특성으로 인해 공간 복잡도는 접근 방식 1과 동일하게 유지됨
--
접근2) 반복
- 재귀로 해결가능하다면 스택으로도 해결 가능
- 각 함수 호출이 호출 스택에 새 프레임을 추가하는 재귀와 달리 스택을 사용하면 재귀의 깊이가 너무 큰 경우(예: 매우 깊은 트리) 스택 오버플로 오류의 위험을 피할 수 있음
- 트리의 루트를 스택에 넣는 것으로 시작 -> 재귀 없이 트리 탐색하는데 도움됨
- 스택에서 맨 위 노드를 반복적으로 가져와 ...
뭐란겨
내 풀이
```java
// 이진 트리 root의 하위 경로를 형성하는지 boolean값을 return
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
// 재귀 NullPointerException -> null 체크로 개선
if (root==null || root.left == null || root.right == null) return false;
boolean subLeft = head.next.equals(root.left);
boolean subRight = head.next.equals(root.right);
// root와 head의 val이 동일한 경우
if (head.val == root.val) {
// 하위 경로를 형성하면 true
if (subLeft || subRight && head == null ) { return true; }
// 아닌 경우 false
// if (!subLeft || !subRight) { return false; }
}
// // 특정 경로에서 하위 경로가 형성되는 경우 true return
if (subLeft || subRight) { return true; }
// if (!subLeft || !subRight) { return false; }
// 다음 head와 root 왼쪽 / 오른쪽 전달하며 재귀한다
return isSubPath(head.next, root.left) || isSubPath(head.next, root.right);
}
}느낀점
- 나는 분명히 논리적으로 맞다고 생각했는데 숨어있는 오류들이 많았고 leetcode 결제를 하지 못해 디버깅할 수 없어 어려웠음
많은 시간을 투자한 점
- 네카라쿠배 회사들 업무가 가능하려면 최소한 미디엄 정도는 혼자 풀어야한다고 생각해서 스스로 해결하려는 시도를 오래 했음 (09.10 ~ 10.22, 약 42일 6주)
- TDD나 for, if문, flag 만으로 무리하게 돌파하려는 약점을 발견했고 자료구조와 알고리즘의 보완이 충분하지 않으면 더이상 무의미하다고 판단하여 일시 멈춤
- gpt나 솔루션을 보고 넘어갈까.. 했지만 아쉬워서 앞으로 좀 더 풀어보고싶다는 생각
- 대신 더이상 시간낭비는 치명적이니 다른 것들 병행하면서
- 소감
- 내 능력으로는 못하는건가.. 아쉬움 많이 노력하고 애정을 투자한만큼
- 씁쓸..
리팩토링
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (root==null) return false;
if (checkPath(head, root)) return true;
return isSubPath(head, root.left) || isSubPath(head, root.right);
}
private boolean checkPath(ListNode head, TreeNode root) {
if (head == null) return true;
if (root == null || head.val != root.val) return false;
return checkPath(head.next, root.left) || checkPath(head.next, root.right);
}
}
근면성실