LeetCode 1367 Linked List in Binary Tree

https://leetcode.com/problems/linked-list-in-binary-tree/

Linked List in Binary Tree - LeetCode

문제에서 이진트리에서 사용될 노드와 링크드리스트의 각 노드 구현 방식이 주어진다.

 

이제 문제해결을 위해 각 케이스들에 대해 생각해 봐야한다. 그리고 필연적으로 재귀함수를 사용하게 될테니, 기저조건(종료조건, 탈출조건)에 대해 먼저 생각해 본다.

 

• 문제의 Constraints를 보면, 노드는 최소 1개는 주어진다. 즉, 재귀함수 내부에서 해당 노드의 값이 비어있는 경우는 없다 (node.val이 null또는 undefined인 경우는 없다) 물론, 값이 비어있을 때는 다음 재귀를 돌지 않도록 필터링해야겠지만, 아예 입력으로 주어질 때부터 체크할 필요는 없다.
• 언제 이 재귀가 끝날 것인가? head의 값과 트리의 값이 같은데, 다음 head가 없는 경우이다. 이 때가 바로 최종 종료조건이 된다.
• 또 다른 탈출조건은 실패조건인데, 아직 체크할 head가 남았지만, left나 right가 없는 경우이다.

위와같은 정도로 기본 기저조건을 설정해둔다. 

 

다음은 내부 로직인데, 중요한 부분은 현재 head의 값이 root의 값과 같더라도 이 점을 탐색 시작점으로 꼭 설정할 필요는 없다는 것이다. 왜냐하면 이 점을 찍고 들어가면 그 다음부터는 계속 값이 일치해야 하기 때문이다. 하지만 이것을 반대로 생각하면, 앞서 일치한 값이 있는 상태라면 지금부터는 값이 다르면 무조건 탈출해야 한다는 말이 된다. 연속적으로 값이 일치해야 하기 때문에.

이를 고려하지 않으면 시간초과가 날 수 있다. 즉, 일종의 flag를 두어 값의 연속 일치를 봐야하는 상태인지 아닌지를 표시하고, flag일 때 불일치가 발생하면 바로바로 탈출하는 기저조건을 추가한다.

 

그리고 이제 flag가 없는 상황에서는:

현재 값이 일치하면 flag를 키고 다음 재귀에 들어가고,

값이 일치하지 않을 때 root의 다음 값들을 들고 재귀에 들어가면 된다.

 

<알고리즘>

재귀함수, 이진트리, 링크드리스트

 

<코드>

자바스크립트(javascript)에서는 재귀 깊이가 1천까지 허용해주는 것으로 알고 있다. 이는 PS에서는 상당히 부족하다고 생각하지만 본 문제 해결에는 충분하다.

const travel = (h, r, flag) => {
    if (h.val === r.val && !h.next) return true
    if (!r.left && !r.right) return false

    if (flag) {
        if (h.val !== r.val) return false
        if (r.left && travel(h.next, r.left, true)) return true
        if (r.right && travel(h.next, r.right, true)) return true
        return false
    }

    if (h.val === r.val && r.left && travel(h.next, r.left, true)) return true
    if (h.val === r.val && r.right && travel(h.next, r.right, true)) return true

    if (r.left && travel(h, r.left, false)) return true
    if (r.right && travel(h, r.right, false)) return true
    return false
}

var isSubPath = function (head, root) {
    return travel(head, root, false)
};