1367. Linked List in Binary Tree
Difficulty: Medium
Topics: Linked List, Tree, Depth-First Search, Breadth-First Search, 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.
Example 1:
Example 2:
Example 3:
Constraints:
Hint:
Solution:
We need to recursively check whether a linked list can match a downward path in a binary tree. We'll use depth-first search (DFS) to explore the binary tree and attempt to match the linked list from its head to the leaf nodes.
Here’s how we can approach the solution:
Let's implement this solution in PHP: 1367. Linked List in Binary Tree
val = $val; $this->next = $next; } } // Definition for a binary tree node. class TreeNode { public $val = 0; public $left = null; public $right = null; function __construct($val = 0, $left = null, $right = null) { $this->val = $val; $this->left = $left; $this->right = $right; } } class Solution { /** * @param ListNode $head * @param TreeNode $root * @return Boolean */ function isSubPath($head, $root) { ... ... ... /** * go to ./solution.php */ } // Helper function to match the linked list starting from the current tree node. function dfs($head, $root) { ... ... ... /** * go to ./solution.php */ } } // Example usage: // Linked List: 4 -> 2 -> 8 $head = new ListNode(4); $head->next = new ListNode(2); $head->next->next = new ListNode(8); // Binary Tree: // 1 // / \ // 4 4 // \ \ // 2 2 // / \ / \ // 1 6 8 8 $root = new TreeNode(1); $root->left = new TreeNode(4); $root->right = new TreeNode(4); $root->left->right = new TreeNode(2); $root->right->left = new TreeNode(2); $root->left->right->left = new TreeNode(1); $root->left->right->right = new TreeNode(6); $root->right->left->right = new TreeNode(8); $root->right->left->right = new TreeNode(8); $solution = new Solution(); $result = $solution->isSubPath($head, $root); echo $result ? "true" : "false"; // Output: true ?>Explanation:
isSubPath($head, $root):
- This function recursively checks whether the linked list starting from $head corresponds to any downward path in the tree.
- It first checks if the current root node is the start of the list (by calling dfs).
- If not, it recursively searches the left and right subtrees.
dfs($head, $root):
- This helper function checks if the linked list matches the tree starting at the current tree node.
- If the list is fully traversed ($head === null), it returns true.
- If the tree node is null or values don’t match, it returns false.
- Otherwise, it continues to check the left and right children.
Example Execution:
For input head = [4,2,8] and root = [1,4,4,null,2,2,null,1,null,6,8], the algorithm will:
This solution efficiently checks for the subpath in the binary tree using DFS.
Contact Links
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
The above is the detailed content of Linked List in Binary Tree. For more information, please follow other related articles on the PHP Chinese website!