1367 Linked List in Binary Tree 二叉树中的链表

Description:

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.

Example:

Example 1:

[图片上传失败...(image-bbdb64-1667111961189)]

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

[图片上传失败...(image-64f01d-1667111961190)]

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

The number of nodes in the tree will be in the range [1, 2500].
The number of nodes in the list will be in the range [1, 100].
1 <= Node.val <= 100 for each node in the linked list and binary tree.

题目描述：

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

示例：

示例 1：

[图片上传失败...(image-7a0911-1667111961190)]

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。

示例 2：

[图片上传失败...(image-1df8f8-1667111961190)]

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true

示例 3：

输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：false
解释：二叉树中不存在一一对应链表的路径。

提示：

二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
链表包含的节点数目在 1 到 100 之间。
二叉树包含的节点数目在 1 到 2500 之间。

思路：

DFS
从链表和二叉树结点值相同的结点开始查找
如果链表找到末尾, 返回 true
如果二叉树找到空结点, 返回 false
如果链表结点的值和二叉树结点的值不相等, 返回 false
否则链表移动到下一个结点, 二叉树可以选择左或者右两条路径
时间复杂度为 O(n ^ 2), 空间复杂度为 O(n), 空间复杂度实际上只需要二叉树的高度

代码:

C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
private:
    bool dfs(ListNode* head,TreeNode* root)
    {
        return !head ? !head : (!root ? !!root : root -> val == head -> val and (dfs(head -> next, root -> left) or dfs(head -> next, root -> right)));
    }
public:
    bool isSubPath(ListNode* head, TreeNode* root) 
    {
        return !head ? !head : (!root ? !!root : dfs(head, root) or isSubPath(head, root -> left) or isSubPath(head, root -> right));
    }
};

Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        return head == null ? head == null : (root == null ? root != null : dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right));
    }
    
    private boolean dfs(ListNode head, TreeNode root) {
        return head == null ? head == null : (root == null ? root != null : root.val == head.val && (dfs(head.next, root.left) || dfs(head.next, 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: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        def dfs(head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
            return not head if not head else not not root if not root else root.val == head.val and (dfs(head.next, root.left) or dfs(head.next, root.right))
        return not head if not head else not not root if not root else dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)