convert-sorted-list-to-binary-search-tree
1308 단어 알고리즘 문제
제목 설명
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
사고방식: 빠른 바늘을 통해 중간 결점을 찾아 중간 결점을 두 갈래 검색 트리에 삽입한 다음에 중간에서 질서정연한 단사슬표를 두 부분으로 뜯어내고 앞부분은 왼쪽 나무, 뒷부분은 오른쪽 나무로 분류한다.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
if(!head){
return nullptr;
}
if(!head->next){
return new TreeNode(head->val);
}
ListNode* fast = head;
ListNode* slow = head;
ListNode* pre = head;
while(fast && fast->next){
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
TreeNode* root = new TreeNode(slow->val);
pre->next = nullptr;
root->left = sortedListToBST(head);
root->right = sortedListToBST(slow->next);
return root;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[못 푼 문제] 백준 10989번sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
