POTD: Leet Code 1367 (Linked List in Binary Tree)

To solve “1367. Linked List in Binary Tree” in JavaScript, we can break the problem down as follows:

• Given the head of a linked list and the root of a binary tree, we need to determine if the linked list exists as a downward path in the binary tree. The path must begin at some node in the binary tree and can only move downwards (left or right).

Plan

1. Depth-First Search (DFS): We’ll use a DFS approach to traverse the tree.
2. Check Path: When we find a node that matches the head of the linked list, we’ll recursively check if the linked list continues to match down the tree.

Solution Code

/**
 * Main function to check if the linked list is a subpath in the binary tree
 * @param {ListNode} head - The head of the linked list
 * @param {TreeNode} root - The root of the binary tree
 * @return {boolean} - Returns true if the linked list is a downward path in the binary tree, otherwise false
 */
var isSubPath = function(head, root) {
    if (!root) return false;

    // Check if there's a matching path starting from this node
    return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
};

/**
 * Helper function to check if we can match the linked list starting from the given tree node
 * @param {ListNode} head - The current node of the linked list
 * @param {TreeNode} root - The current node of the binary tree
 * @return {boolean} - Returns true if the linked list matches from this point in the tree
 */
function dfs(head, root) {
    // If we've matched the whole linked list, return true
    if (!head) return true;
    // If the tree node is null or the values don't match, return false
    if (!root || head.val !== root.val) return false;

    // Continue matching the linked list down the left or right subtree
    return dfs(head.next, root.left) || dfs(head.next, root.right);
}

Explanation

• The isSubPath function checks if the linked list exists as a path starting from the current binary tree node (root) or from one of its children (root.left, root.right).
• The dfs function is used to check if the linked list can be matched starting from a given binary tree node. It recursively moves down the tree, trying to match the linked list.
• If we successfully match all nodes of the linked list (!head), we return true.

Time Complexity:

• Traversing the tree takes O(N), where N is the number of nodes in the binary tree.
• For each node in the tree, we may compare it with up to L nodes in the linked list, where L is the length of the linked list.
• So the time complexity is O(N * L).