Repository navigation
Expand file tree
/
Copy pathlc_109.cpp
More file actions
71 lines (65 loc) · 1.42 KB
/
Copy pathlc_109.cpp
File metadata and controls
71 lines (65 loc) · 1.42 KB
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildBinaryTree( vector<int>& ele, int s, int e)
{
if( s == e)
{
TreeNode* node = new TreeNode(ele[s]);
return node;
}
if( s > e)
return NULL;
int mid = (e - s )/2 + s;
TreeNode* root = new TreeNode(ele[mid]);
root->left = buildBinaryTree( ele, s , mid - 1);
root->right = buildBinaryTree( ele, mid + 1, e);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
vector<int> sortArray;
while( head )
{
sortArray.push_back(head->val);
head = head->next;
}
return buildBinaryTree(sortArray, 0, sortArray.size() - 1);
}
};
/**
*>>ÓÅÏȼ¶Ð¡ÓÚ+-
*O(1) space solution
*TreeNode * DFS(int len, int current, ListNode **curr) {
*
* TreeNode *node = new TreeNode(0);
*
* if(current * 2 + 1 <= len - 1) {
* node->left = DFS(len, current * 2 + 1, curr);
* }
*
* node->val = (*curr)->val;
* *curr = (*curr)->next;
*
* if(current * 2 + 2 <= len - 1) {
* node->right = DFS(len, current * 2 + 2, curr);
* }
*
* return node;
* }
*/