Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
|
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 |
/** * 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 *DFS(vector<int> &arr,int
left,int
right) { if(right<left) return
NULL; int
mid=(right+left)>>1; //每次从表头开始遍历链表寻找中间结点超时 TreeNode *root=new
TreeNode(arr[mid]); root->left=DFS(arr,left,mid-1); root->right=DFS(arr,mid+1,right); return
root; } TreeNode *sortedListToBST(ListNode *head) { ListNode *p=head; vector<int> arr; while(p) { arr.push_back(p->val); p=p->next; } return
DFS(arr,0,arr.size()-1); }}; |
[LeetCode]Convert Sorted List to Binary Search Tree,布布扣,bubuko.com
[LeetCode]Convert Sorted List to Binary Search Tree
原文：http://www.cnblogs.com/Rosanna/p/3595737.html