LeetCode 1367: Linked List in Binary Tree Solution

Master LeetCode problem 1367 (Linked List in Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1367. Linked List in Binary Tree

Medium

Linked List Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

We can traverse the binary tree in a depth-first manner and at each node, check if it matches the linked list starting from the head.
To check if a path in the binary tree matches the linked list, we can recursively check if the current node matches the current element in the linked list and then move to its left and right child nodes accordingly.
If we find a match for the entire linked list starting from the head, we return true. Otherwise, we continue searching in the binary tree.
We need to handle cases where the linked list is a subpath of a longer path in the binary tree.

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. Space Complexity: O(H) where H is the height of the binary tree.

Solution Code

class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) return false;
        return isSubPathFromCurrentNode(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    
    private boolean isSubPathFromCurrentNode(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        if (head.val != root.val) return false;
        return isSubPathFromCurrentNode(head.next, root.left) || isSubPathFromCurrentNode(head.next, root.right);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1367 (Linked List in Binary Tree)?

This page provides optimized solutions for LeetCode problem 1367 (Linked List in Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1367 (Linked List in Binary Tree)?

The time complexity for LeetCode 1367 (Linked List in Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1367 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1367 in Java, C++, or Python.

Back to LeetCode Solutions