모르면 물어본다
문제 정의
Given a binary tree root and a linked list with head as the first node.
Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.
In this context downward path means a path that starts at some node and goes downwards.
Example 1:
Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.
Example 2:
Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Example 3:
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]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.
Constraints:
The number of nodes in the tree will be in the range [1, 2500].
The number of nodes in the list will be in the range [1, 100].
1 <= Node.val <= 100 for each node in the linked list and binary tree.
- 연결리스트 head와 이진트리 root가 주어졌을 때, 특정 하위 경로로 연결되는 경우 true를 아닌 경우 false를 return 해주는 문제
내 생각
- while 또는 재귀로 트리를 순회하며 root의 요소를 비교한다
- true인 경우 / false인 경우를 정의한다
- 1 head.next가 root.left || root.right와 불일치하는 경우 하위 경로 형성이 유효하지 않으므로 false를 return 한다
2.2 head.next가 root.left || root.right과 일치하는 경우 하위 경로 형성이 유효하므로 true를 return 한다 - 검증
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (head.next == root.left) return true;
return false;
}
}문제1
error: incomparable types: ListNode and TreeNode- head.next와 root.left || root.right는 각각 비교불가능한 데이터 타입
println()으로 출력해본 결과 값이 아닌 주소가 출력됨- 이걸 어떻게 한담..?? -> listnode와 treenode 비교를 해야하니 각각 int로 형변환 시도
이진트리와 단일 연결 리스트의 구조적 특성 이해
- 트리는 계층 구조 (노드 -> 자식 노드 방향)
- 연결리스트는 선형 구조 (노드 -> 다음 노드 방향)
- 트리 구조의 각 노드를 탐색하는 동안 리스트 노드가 순차적으로 일치하는지 여부를 확인하는 것이 문제의 핵심이라고..
- chat gpt가 설명함
- 그러니 리스트의 각 노드를 트리의 특정 경로와 비교해야 한다는 요구사항이 도출된다능..
- 와 요즘 인공지능 성능 미쳤네.. 그래서 이런 접근을 인지하는 과정을 설명해달라고 함. 파라미터 많은게 최고인지 궁금해서
- 유사한 패턴을 인식하고 기계학습 알고리즘을 통해 다양한 문제 해결 경험이 쌓여서 응용가능하다고.. 대화해볼수록 개똑똑함..
본것, 깨달은 것, 적용한 것
--
내가 어려웠던 점
새롭게 알게된 점
