题目链接
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
代码
class Solution {
public:
ListNode* head;
int size(ListNode* head) {
int cnt = 0;
while (head != NULL) {
cnt++;
head = head->next;
}
return cnt;
}
TreeNode* dfs(int s, int e) {
if (s > e) {
return NULL;
}
int m = (s + e) / 2;
TreeNode* left = dfs(s, m - 1);
TreeNode* parent = new TreeNode(head->val);
parent->left = left;
head = head->next;
parent->right = dfs(m + 1, e);
cout<<parent->val<<endl;
return parent;
}
TreeNode* sortedListToBST(ListNode* head) {
this->head = head;
int cnt = size(head);
return dfs(0, cnt - 1);
}
};
