1367. Linked List in Binary Tree

MediumView on LeetCode

Linked List Tree Depth-First Search Binary Tree

Time: O(n·m)

Space: O(n)

Intuition

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

Algorithm

1For each tree node: try matching linked list starting from head.
2dfs(treeNode, listNode): if listNode==null, return true. If treeNode==null, return false.
3If values match: recurse dfs(left,next) || dfs(right,next).
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

// 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?