이진 트리의 연결 목록

1367. 이진트리의 연결리스트

난이도:중

주제: 연결 리스트, 트리, 깊이 우선 검색, 너비 우선 검색, 이진 트리

이진 트리 루트와 head가 첫 번째 노드인 연결 리스트가 주어졌습니다.

헤드에서 시작하는 연결 목록의 모든 요소가 이진 트리에 연결된 일부 하향 경로에 해당하면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

이 맥락에서 하향 경로는 어떤 노드에서 시작하여 아래로 내려가는 경로를 의미합니다.

예 1:

• 입력: 헤드 = [4,2,8], 루트 = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null ,1,3]
• 출력: true
• 설명: 파란색 노드는 바이너리 트리의 하위 경로를 형성합니다.

예 2:

• 입력: 헤드 = [1,4,2,6], 루트 = [1,4,4,null,2,2,null,1,null,6,8,null,null,null ,null,1,3]
• 출력: true

예 3:

• 입력: 헤드 = [1,4,2,6,8], 루트 = [1,4,4,null,2,2,null,1,null,6,8,null,null ,null,null,1,3]
• 출력: false
• 설명: 이진 트리에는 head에서 연결된 목록의 모든 요소를 ​​포함하는 경로가 없습니다.

제약조건:

• 트리의 노드 수는 [1, 2500] 범위에 있습니다.
• 목록의 노드 수는 [1, 100] 범위에 있습니다.
• 1

힌트:

1. 연결된 목록의 포인터와 이진 트리의 노드가 주어지면 재귀 함수를 만듭니다. 헤드부터 시작하는 연결 목록의 모든 요소가 이진 트리의 일부 하향 경로에 해당하는지 확인하세요.

해결책:

연결된 목록이 이진 트리의 하향 경로와 일치할 수 있는지 재귀적으로 확인해야 합니다. 깊이 우선 검색(DFS)을 사용하여 이진 트리를 탐색하고 헤드부터 리프 노드까지 연결된 목록을 일치시키려고 시도합니다.

해결책에 접근하는 방법은 다음과 같습니다.

단계:

1. 연결된 목록을 일치시키는 재귀 함수: 연결된 목록 노드와 트리 노드를 사용하는 도우미 함수를 만듭니다. 현재 노드에서 시작하는 연결 리스트가 이진 트리의 하향 경로와 일치하는지 확인하는 함수입니다.
2. 트리를 통한 DFS: DFS를 사용하여 이진 트리를 탐색하고 각 노드에서 해당 노드부터 시작하여 일치하는 항목이 있는지 확인합니다.
3. 기본 조건: 연결 목록이 완전히 탐색되면 재귀가 중지되고 true를 반환해야 하며, 이진 트리 노드가 null이거나 값이 일치하지 않으면 false를 반환해야 합니다.
4. 모든 노드에서 검색 시작: 모든 트리 노드에서 일치 확인을 시작하여 연결된 목록의 잠재적인 시작 지점을 찾습니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1367. 이진트리의 연결리스트

<?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
?>

설명:

1. isSubPath($head, $root):

   • 이 함수는 $head로 시작하는 연결 목록이 트리의 하향 경로에 해당하는지를 재귀적으로 확인합니다.
   • 먼저 현재 루트 노드가 목록의 시작인지 확인합니다(dfs를 호출하여).
   • 그렇지 않으면 왼쪽과 오른쪽 하위 트리를 재귀적으로 검색합니다.

2. dfs($head, $root):

   • 이 도우미 함수는 연결된 목록이 현재 트리 노드에서 시작하는 트리와 일치하는지 확인합니다.
   • 목록이 완전히 순회되면($head === null) true를 반환합니다.
   • 트리 노드가 null이거나 값이 일치하지 않으면 false를 반환합니다.
   • 그렇지 않으면 왼쪽과 오른쪽 자식을 계속해서 검사합니다.

실행 예:

입력 헤드 = [4,2,8] 및 루트 = [1,4,4,null,2,2,null,1,null,6,8]의 경우 알고리즘은 다음을 수행합니다.

• 루트(노드 1)에서 시작하여 일치에 실패합니다.
• 왼쪽 하위(노드 4)로 이동하여 4를 일치시킨 다음 아래로 이동하여 2를 일치시키고 8을 일치시켜 true를 반환합니다.

복잡성:

• 시간 복잡도: O(N * min(L, H)), 여기서 N은 이진 트리의 노드 수, L은 연결 목록의 길이, H는 이진 트리의 높이입니다. 나무.
• 공간 복잡도: 이진 트리의 재귀 깊이로 인해 O(H)

이 솔루션은 DFS를 사용하여 바이너리 트리의 하위 경로를 효율적으로 검사합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 이진 트리의 연결 목록의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!