SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a singly linked list and a binary tree, the task is to check whether the linked list is a subpath of the binary tree. A subpath is defined as a sequence of nodes in the binary tree that matches the sequence in the linked list.

The goal is to determine if there exists a path starting from any node in the tree that matches the entire sequence of the linked list.

Intuition

The problem can be viewed as trying to match the sequence of linked list nodes with paths in the binary tree. A recursive depth-first search (DFS) traversal is useful here, where at each step, we check if the current node in the binary tree matches the current node in the linked list. If so, we try to match the next node in the list with the next nodes in the tree.

If there’s a mismatch, the recursion should restart from the next node in the tree but try matching from the head of the linked list again.

Approach

1. Recursive DFS Traversal:

   • We begin a recursive traversal on the binary tree and check if the current node in the tree matches the current node in the linked list.
   • If there’s a match, we continue with the next node of the linked list and both left and right children of the tree node.
   • If a node doesn’t match, we try to match the next tree node with the head of the linked list again.

2. Base Cases:

   • If we reach the end of the linked list (i.e., all nodes are matched), we return True.
   • If we reach a null node in the tree, we return False.

3. Edge Case:

   • The solution should handle scenarios where the linked list starts matching at any point in the tree.

Complexity

Time Complexity:

O(n * m), where n is the number of nodes in the binary tree and m is the number of nodes in the linked list. In the worst case, we may need to check each node of the tree for potential subpath matching.

Space Complexity:

O(n), due to the recursion stack in the depth-first traversal, where n is the height of the tree.

Code

C++

class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        return dfs(head, head, root);
    }
    
    bool dfs(ListNode* head, ListNode* cur, TreeNode* root) {
        if (cur == nullptr) return true;
        if (root == nullptr) return false;

        if (cur->val == root->val) {
            cur = cur->next;
        } else if (head->val == root->val) {
            head = head->next;
        } else {
            cur = head;
        }

        return dfs(head, cur, root->left) || dfs(head, cur, root->right);
    }
};

Python

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        return self.dfs(head, head, root)
    
    def dfs(self, head: ListNode, cur: ListNode, root: TreeNode) -> bool:
        if cur is None:
            return True
        if root is None:
            return False

        if cur.val == root.val:
            cur = cur.next
        elif head.val == root.val:
            head = head.next
        else:
            cur = head

        return self.dfs(head, cur, root.left) or self.dfs(head, cur, root.right)

Java

class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        return dfs(head, head, root);
    }

    private boolean dfs(ListNode head, ListNode cur, TreeNode root) {
        if (cur == null) return true;
        if (root == null) return false;

        if (cur.val == root.val) {
            cur = cur.next;
        } else if (head.val == root.val) {
            head = head.next;
        } else {
            cur = head;
        }

        return dfs(head, cur, root.left) || dfs(head, cur, root.right);
    }
}

JavaScript

/**
 * 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)
 * }
 */
var isSubPath = function (head, root) {
    return dfs(head, head, root);
};

var dfs = function (head, cur, root) {
    if (cur === null) return true;  // Successfully matched the list
    if (root === null) return false; // Reached the end of the tree without matching

    if (cur.val === root.val) {
        cur = cur.next;  // Move to the next list node if value matches
    } else if (head.val === root.val) {
        head = head.next; // Start new matching attempt if the value matches head of list
    } else {
        cur = head;  // Reset the matching pointer
    }

    // Recursively check left and right subtrees
    return dfs(head, cur, root.left) || dfs(head, cur, root.right);
};