LeetCode 1367. Linked List in Binary Tree

, , , ,

Question

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Solution

Only need to check possible start position and then use DFS traversal the tree and LinkedList.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// time: O(n * min(L, H)) L: length of list, H = tree Height
    // space:O(H)
public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null && root == null)
            return true;
        if (head == null || root == null)
            return false;
        if (head.val == root.val) {
            if (dfs(head, root))
                return true;
            else
                return isSubPath(head, root.left) || isSubPath(head, root.right);
        } else {
            return isSubPath(head, root.left) || isSubPath(head, root.right);
        }
    }

public boolean dfs(ListNode head, TreeNode root) {
        if (head == null)
            return true;
        if (root == null && head != null)
            return false;
        if (root != null && head != null && head.val != root.val)
            return false;
        boolean left = dfs(head.next, root.left);
        boolean right = dfs(head.next, root.right);
        return left || right;
    }