aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--linked_list_binary_tree.c44
-rw-r--r--linked_list_binary_tree.py104
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,
+ ],
+ )
+ )