[Medium] 1367. Linked List in Binary Tree

문제

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.

 

이진 트리 루트와 헤드를 첫 번째 노드로 하는 링크된 목록이 제공됩니다. 
머리글에서 시작하는 링크된 목록의 모든 요소가 이진 트리에 연결된 일부 하향 경로에 해당하면 True를 반환하고 그렇지 않으면 False를 반환합니다.
이 맥락에서 하향 경로는 특정 노드에서 시작하여 하향으로 가는 경로를 의미한다.

 

예시

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.

 

풀이 과정

노드를 탐색하며 linked list가 연결되어 있는지 확인한다.

이때 노드가 linked list에 연결되어 있지 않으면 left, right 노드로 탐색을 진행한다.

모든 노드 탐색을 완료하면 false를 반환한다.

풀이 코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSubPath = function(head, root) {
    if (!head || !root) {
        return false;
    }

    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (compare(head, node)) {
            return true;
        }
        
        if (node.left) {
            stack.push(node.left);
        }
        
        if (node.right) {
            stack.push(node.right);
        }
    }
    
    return false;
};

function compare(item, node) {
    if (!item) {
        return true;
    }
    
    if (!node) {
        return false;
    }

    if (item.val !== node.val) {
        return false;
    }

    return compare(item.next, node.left) || compare(item.next, node.right);
}