DDSA Solutions

1367. Linked List in Binary Tree

MediumView on LeetCode
Linked ListTreeDepth-First SearchBinary Tree
Time: O(n·m)
Space: O(n)

Problem Overview

DFS the tree.

Intuition

DFS the tree. At each node, try to continue the current linked list match or restart from the head of the list.

Algorithm

  1. 1For each tree node: try matching linked list starting from head.
  2. 2dfs(treeNode, listNode): if listNode==null, return true. If treeNode==null, return false.
  3. 3If values match: recurse dfs(left,next) || dfs(right,next).
  4. 4Also try starting fresh: isSubPath(head, treeNode.left) || isSubPath(head, treeNode.right).

Common Pitfalls

  • •Must try restarting the list match at each tree node, not just continue existing match.
1367.cs
C#
// Approach: For each tree node try matching the linked list head starting there; DFS checks if all list nodes match a root-to-leaf path.
// Time: O(n·m) Space: O(n)

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public bool IsSubPath(ListNode head, TreeNode root)
    {
        if (root == null)
            return false;

        return IsContinuousSubPath(head, root) || IsSubPath(head, root.left) || IsSubPath(head, root.right);
    }

    private bool IsContinuousSubPath(ListNode head, TreeNode root)
    {
        if (head == null)
            return true;

        if (root == null)
            return false;

        return head.val == root.val && (IsContinuousSubPath(head.next, root.left) || IsContinuousSubPath(head.next, root.right));
    }
}
Was this solution helpful?

Related Problems