diff options
-rw-r--r-- | linked_list_binary_tree.c | 44 | ||||
-rw-r--r-- | linked_list_binary_tree.py | 104 |
2 files changed, 148 insertions, 0 deletions
diff --git a/linked_list_binary_tree.c b/linked_list_binary_tree.c new file mode 100644 index 0000000..9ccca03 --- /dev/null +++ b/linked_list_binary_tree.c @@ -0,0 +1,44 @@ +// 1367. Linked List in Binary Tree +#include "leetcode.h" + +/* + * 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. + */ + +bool findSubPath(struct ListNode *head, struct TreeNode *root) { + if (!head) + return true; + if (!root) + return false; + return head->val == root->val && (findSubPath(head->next, root->left) || + findSubPath(head->next, root->right)); +} + +bool isSubPath(struct ListNode *head, struct TreeNode *root) { + if (!root) + return false; + return findSubPath(head, root) || isSubPath(head, root->left) || + isSubPath(head, root->right); +} + +int main() { + struct ListNode *head = listnode_create(1); + head->next = listnode_create(4); + head->next->next = listnode_create(2); + head->next->next->next = listnode_create(6); + struct TreeNode *root = treenode_create(1); + root->left = treenode_create(4); + root->right = treenode_create(4); + root->left->right = treenode_create(2); + root->right->left = treenode_create(2); + root->left->right->left = treenode_create(1); + root->right->left->left = treenode_create(6); + root->right->left->right = treenode_create(8); + root->right->left->right->left = treenode_create(1); + root->right->left->right->right = treenode_create(3); + printf("%d\n", isSubPath(head, root)); // expect: 1 +} diff --git a/linked_list_binary_tree.py b/linked_list_binary_tree.py new file mode 100644 index 0000000..b9e8bd0 --- /dev/null +++ b/linked_list_binary_tree.py @@ -0,0 +1,104 @@ +# 1367. Linked List in Binary Tree + +""" +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. +""" + + +# Definition for singly-linked list. +class ListNode(object): + def __init__(self, val=0, next=None): + self.val = val + self.next = next + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + def isSubPath(self, head, root): + """ + :type head: ListNode + :type root: TreeNode + :rtype: bool + """ + + def dfs(head, root): + if not head: + return True + if not root: + return False + return root.val == head.val and ( + dfs(head.next, root.left) or dfs(head.next, root.right) + ) + + if not head: + return True + if not root: + return False + return ( + dfs(head, root) + or self.isSubPath(head, root.left) + or self.isSubPath(head, root.right) + ) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.isSubPath( + head=[4, 2, 8], + root=[ + 1, + 4, + 4, + None, + 2, + 2, + None, + 1, + None, + 6, + 8, + None, + None, + None, + None, + 1, + 3, + ], + ) + ) + print( + obj.isSubPath( + head=[1, 4, 2, 6], + root=[ + 1, + 4, + 4, + None, + 2, + 2, + None, + 1, + None, + 6, + 8, + None, + None, + None, + None, + 1, + 3, + ], + ) + ) |