Home Backend Development PHP Tutorial Linked List in Binary Tree

Linked List in Binary Tree

Sep 07, 2024 pm 06:30 PM

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:

Linked List in Binary Tree

  • 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:

Linked List in Binary Tree

  • 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.

Hint:

  1. Create recursive function, given a pointer in a Linked List and any node in the Binary Tree. Check if all the elements in the linked list starting from the head correspond to some downward path in the binary tree.

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:

Steps:

  1. Recursive function to match linked list: Create a helper function that takes a linked list node and a tree node. This function checks if the linked list starting from the current node matches a downward path in the binary tree.
  2. DFS through the tree: Traverse the binary tree using DFS, and at each node, check if there is a match starting from that node.
  3. Base conditions: The recursion should stop and return true if the linked list is fully traversed, and return false if the binary tree node is null or the values do not match.
  4. Start search at every node: Begin the match check at every tree node to find potential starting points for the linked list.

Let's implement this solution in PHP: 1367. Linked List in Binary Tree

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

<!--?php

// Definition for a singly-linked list node.

class ListNode {

    public $val = 0;

    public $next = null;

    function __construct($val = 0, $next = null) {

        $this--->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

?>

 

 

 

 

<h3>

   

   

  Explanation:

</h3>

 

<ol>

<li>

<p><strong>isSubPath($head, $root)</strong>:</p>

 

<ul>

<li>This function recursively checks whether the linked list starting from $head corresponds to any downward path in the tree.</li>

<li>It first checks if the current root node is the start of the list (by calling dfs).</li>

<li>If not, it recursively searches the left and right subtrees.</li>

</ul>

</li>

<li>

<p><strong>dfs($head, $root)</strong>:</p>

 

<ul>

<li>This helper function checks if the linked list matches the tree starting at the current tree node.</li>

<li>If the list is fully traversed ($head === null), it returns true.</li>

<li>If the tree node is null or values don’t match, it returns false.</li>

<li>Otherwise, it continues to check the left and right children.</li>

</ul>

</li>

</ol>

 

<h3>

   

   

  Example Execution:

</h3>

 

<p>For input head = [4,2,8] and root = [1,4,4,null,2,2,null,1,null,6,8], the algorithm will:</p>

 

<ul>

<li>Start at the root (node 1), fail to match.</li>

<li>Move to the left child (node 4), match 4, then move down and match 2, then match 8, returning true.</li>

</ul>

 

<h3>

   

   

  Complexity:

</h3>

 

<ul>

<li>

<strong>Time Complexity</strong>: O(N * min(L, H)), where N is the number of nodes in the binary tree, L is the length of the linked list, and H is the height of the binary tree.</li>

<li>

<strong>Space Complexity</strong>: O(H) due to the recursion depth of the binary tree.</li>

</ul>

 

<p>This solution efficiently checks for the subpath in the binary tree using DFS.</p>

 

<p><strong>Contact Links</strong></p>

<p>Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi <strong>repositori</strong> bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!</p>

 

<p>Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:</p>

 

<ul>

<li><strong>LinkedIn</strong></li>

<li><strong>GitHub</strong></li>

</ul>

 

 

           

 

             

   

 

             

         

<p>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!</p>

 

 

                        

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Explain JSON Web Tokens (JWT) and their use case in PHP APIs. Explain JSON Web Tokens (JWT) and their use case in PHP APIs. Apr 05, 2025 am 12:04 AM

JWT is an open standard based on JSON, used to securely transmit information between parties, mainly for identity authentication and information exchange. 1. JWT consists of three parts: Header, Payload and Signature. 2. The working principle of JWT includes three steps: generating JWT, verifying JWT and parsing Payload. 3. When using JWT for authentication in PHP, JWT can be generated and verified, and user role and permission information can be included in advanced usage. 4. Common errors include signature verification failure, token expiration, and payload oversized. Debugging skills include using debugging tools and logging. 5. Performance optimization and best practices include using appropriate signature algorithms, setting validity periods reasonably,

What are Enumerations (Enums) in PHP 8.1? What are Enumerations (Enums) in PHP 8.1? Apr 03, 2025 am 12:05 AM

The enumeration function in PHP8.1 enhances the clarity and type safety of the code by defining named constants. 1) Enumerations can be integers, strings or objects, improving code readability and type safety. 2) Enumeration is based on class and supports object-oriented features such as traversal and reflection. 3) Enumeration can be used for comparison and assignment to ensure type safety. 4) Enumeration supports adding methods to implement complex logic. 5) Strict type checking and error handling can avoid common errors. 6) Enumeration reduces magic value and improves maintainability, but pay attention to performance optimization.

How does session hijacking work and how can you mitigate it in PHP? How does session hijacking work and how can you mitigate it in PHP? Apr 06, 2025 am 12:02 AM

Session hijacking can be achieved through the following steps: 1. Obtain the session ID, 2. Use the session ID, 3. Keep the session active. The methods to prevent session hijacking in PHP include: 1. Use the session_regenerate_id() function to regenerate the session ID, 2. Store session data through the database, 3. Ensure that all session data is transmitted through HTTPS.

Describe the SOLID principles and how they apply to PHP development. Describe the SOLID principles and how they apply to PHP development. Apr 03, 2025 am 12:04 AM

The application of SOLID principle in PHP development includes: 1. Single responsibility principle (SRP): Each class is responsible for only one function. 2. Open and close principle (OCP): Changes are achieved through extension rather than modification. 3. Lisch's Substitution Principle (LSP): Subclasses can replace base classes without affecting program accuracy. 4. Interface isolation principle (ISP): Use fine-grained interfaces to avoid dependencies and unused methods. 5. Dependency inversion principle (DIP): High and low-level modules rely on abstraction and are implemented through dependency injection.

Explain late static binding in PHP (static::). Explain late static binding in PHP (static::). Apr 03, 2025 am 12:04 AM

Static binding (static::) implements late static binding (LSB) in PHP, allowing calling classes to be referenced in static contexts rather than defining classes. 1) The parsing process is performed at runtime, 2) Look up the call class in the inheritance relationship, 3) It may bring performance overhead.

What is REST API design principles? What is REST API design principles? Apr 04, 2025 am 12:01 AM

RESTAPI design principles include resource definition, URI design, HTTP method usage, status code usage, version control, and HATEOAS. 1. Resources should be represented by nouns and maintained at a hierarchy. 2. HTTP methods should conform to their semantics, such as GET is used to obtain resources. 3. The status code should be used correctly, such as 404 means that the resource does not exist. 4. Version control can be implemented through URI or header. 5. HATEOAS boots client operations through links in response.

How do you handle exceptions effectively in PHP (try, catch, finally, throw)? How do you handle exceptions effectively in PHP (try, catch, finally, throw)? Apr 05, 2025 am 12:03 AM

In PHP, exception handling is achieved through the try, catch, finally, and throw keywords. 1) The try block surrounds the code that may throw exceptions; 2) The catch block handles exceptions; 3) Finally block ensures that the code is always executed; 4) throw is used to manually throw exceptions. These mechanisms help improve the robustness and maintainability of your code.

What are anonymous classes in PHP and when might you use them? What are anonymous classes in PHP and when might you use them? Apr 04, 2025 am 12:02 AM

The main function of anonymous classes in PHP is to create one-time objects. 1. Anonymous classes allow classes without names to be directly defined in the code, which is suitable for temporary requirements. 2. They can inherit classes or implement interfaces to increase flexibility. 3. Pay attention to performance and code readability when using it, and avoid repeatedly defining the same anonymous classes.

See all articles