1367. Linked List in Binary Tree Medium

1/**
2 * [1367] Linked List in Binary Tree
3 *
4 * Given a binary tree root and a linked list with head as the first node. 
5 * 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.
6 * In this context downward path means a path that starts at some node and goes downwards.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/02/12/sample_1_1720.png" style="width: 220px; height: 280px;" />
10 * 
11 * Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
12 * Output: true
13 * Explanation: Nodes in blue form a subpath in the binary Tree.  
14 * 
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2020/02/12/sample_2_1720.png" style="width: 220px; height: 280px;" />
17 * 
18 * Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
19 * Output: true
20 * 
21 * Example 3:
22 * 
23 * 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]
24 * Output: false
25 * Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	The number of nodes in the tree will be in the range [1, 2500].
31 * 	The number of nodes in the list will be in the range [1, 100].
32 * 	1 <= Node.val <= 100 for each node in the linked list and binary tree.
33 * 
34 */
35pub struct Solution {}
36use crate::util::linked_list::{ListNode, to_list};
37use crate::util::tree::{TreeNode, to_tree};
38
39// problem: https://leetcode.com/problems/linked-list-in-binary-tree/
40// discuss: https://leetcode.com/problems/linked-list-in-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44// Definition for singly-linked list.
45// #[derive(PartialEq, Eq, Clone, Debug)]
46// pub struct ListNode {
47//   pub val: i32,
48//   pub next: Option<Box<ListNode>>
49// }
50// 
51// impl ListNode {
52//   #[inline]
53//   fn new(val: i32) -> Self {
54//     ListNode {
55//       next: None,
56//       val
57//     }
58//   }
59// }
60// Definition for a binary tree node.
61// #[derive(Debug, PartialEq, Eq)]
62// pub struct TreeNode {
63//   pub val: i32,
64//   pub left: Option<Rc<RefCell<TreeNode>>>,
65//   pub right: Option<Rc<RefCell<TreeNode>>>,
66// }
67// 
68// impl TreeNode {
69//   #[inline]
70//   pub fn new(val: i32) -> Self {
71//     TreeNode {
72//       val,
73//       left: None,
74//       right: None
75//     }
76//   }
77// }
78use std::rc::Rc;
79use std::cell::RefCell;
80impl Solution {
81    pub fn is_sub_path(head: Option<Box<ListNode>>, root: Option<Rc<RefCell<TreeNode>>>) -> bool {
82        false
83    }
84}
85
86// submission codes end
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn test_1367() {
94    }
95}
96