솔루션: 정렬된 목록을 이진 검색 트리로 변환

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #109(중간): 정렬된 목록을 이진 검색 트리로 변환

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

예:

Example 1:
Input:	head = [-10,-3,0,5,9]
Output:	[0,-3,9,-10,null,5]
Explanation:	One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
Visual:

Example 2:
Input:	head = []
Output:	[]

Example 3:
Input:	head = [0]
Output:	[0]

Example 4:
Input:	head = [1,3]
Output:	[3,1]

제약:

• The number of nodes in head is in the range [0, 2 * 10^4].
• -10^5 <= Node.val <= 10^5

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

높이 균형 이진 트리를 구축하려면 전체 노드 수의 대략 절반이 루트의 양쪽에 있는지 확인해야 하며 전체 노드 수의 절반을 알 수 있는 유일한 방법은 다음을 찾는 것입니다. 먼저 총 노드 수입니다.

이를 염두에 두고 한 가지 쉬운 해결책은 연결 목록을 배열로 변환하는 것입니다. 그러면 배열의 전체 길이뿐만 아니라 노드 값에 대한 인덱스 액세스도 편리하게 액세스할 수 있습니다. 그 시점에서 중간 노드에서 트리를 빌드하는 재귀 도우미를 정의하고 중간 노드의 왼쪽과 오른쪽에 있는 노드에서 하위 트리를 빌드하기 위해 자신을 재귀적으로 호출할 수 있습니다. 이 옵션을 완료하려면 추가 O(N) 공간이 필요합니다.

그렇게 많은 추가 공간을 사용하지 않으려면 연결 목록을 유지하고 각 재귀 단계에서 중간 노드를 쉽게 찾기 위해 Floyd의 주기 감지 알고리즘을 사용하여 배열의 인덱스 액세스 특성을 잃을 수 있습니다. 그러나 이렇게 하려면 연결된 목록의 일부를 반복적으로 반복해야 하므로 시간 복잡도가 O(N)에서 O(N log N)로 높아집니다.

그러나 우리는 더 잘할 수 있습니다. O(log N) 추가 공간(출력 공간 초과)만 있으면 O(N) 시간에 이 문제를 완료할 수 있습니다.

먼저 총 노드 수(카운트)를 계산하기 위해 연결 목록을 한 번 반복해야 합니다. 그런 다음 인덱스 번호를 인수로 사용하여 재귀 도우미(treeify())를 정의할 수 있습니다. 인덱스 번호로 리스트노드에 직접 액세스할 수는 없지만, 반복 순서로 액세스하도록 강제하기 위해 중위 트리 순회를 이용할 수 있습니다.

재귀를 통해 제대로 업데이트하려면 목록 포인터(curr)에 전역 범위가 있어야 합니다. 중위 순회에서는 왼쪽 하위 트리를 재귀적으로 처리한 다음 중간 노드를 처리한 다음 오른쪽 하위 트리를 재귀적으로 처리합니다. 이 솔루션의 경우 중간 노드 처리가 끝날 때 curr을 curr.next로 이동해야 합니다.

그런 다음 재귀 도우미가 만든 전체 트리를 반환할 수 있습니다.

시간 복잡도: O(N) 여기서 N은 연결된 목록의 길이입니다

.

공간 복잡성: 재귀 스택으로 인해 입력/출력에 필요한 공간을 초과하는 O(log N)

구현:

Python의 경우 목록 인덱스 포인터(curr)를 목록에 저장하여 제대로 업데이트되도록 전역 범위를 제공할 수 있습니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var sortedListToBST = function(head) {
    let curr = head, count = 0
    while (curr) curr = curr.next, count++
    const treeify = (i, j) => {
        if (j < i) return null
        let mid = i + j >> 1, node = new TreeNode()
        node.left = treeify(i, mid - 1)
        node.val = curr.val, curr = curr.next
        node.right = treeify(mid + 1, j)
        return node
    }
    curr = head
    return treeify(1, count)
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        curr, count = head, 0
        while curr:
            curr = curr.next
            count += 1
        def treeify(i: int, j: int) -> TreeNode:
            if j < i: return None
            mid, node = i + j >> 1, TreeNode()
            node.left = treeify(i, mid - 1)
            node.val, curr[0] = curr[0].val, curr[0].next
            node.right = treeify(mid + 1, j)
            return node
        curr = [head]
        return treeify(1, count)

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    ListNode curr;
    public TreeNode sortedListToBST(ListNode head) {
        int count = 0;
        curr = head;
        while (curr != null) {
            curr = curr.next;
            count++;
        }
        curr = head;
        return treeify(1, count);
    }
    private TreeNode treeify(int i, int j) {
        if (j < i) return null;
        int mid = i + j >> 1;
        TreeNode node = new TreeNode();
        node.left = treeify(i, mid - 1);
        node.val = curr.val;
        curr = curr.next;
        node.right = treeify(mid + 1, j);
        return node;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
private:
    ListNode* curr;
    TreeNode* treeify(int i, int j) {
        if (j < i) return nullptr;
        int mid = (i + j) >> 1;
        TreeNode* node = new TreeNode();
        node->left = treeify(i, mid - 1);
        node->val = curr->val, curr = curr->next;
        node->right = treeify(mid + 1, j);
        return node;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int count = 0;
        curr = head;
        while (curr) curr = curr->next, count++;
        curr = head;
        return treeify(1, count);
    }
};