-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.hpp
More file actions
102 lines (82 loc) · 1.89 KB
/
Solution.hpp
File metadata and controls
102 lines (82 loc) · 1.89 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//
// Created by CFWLoader on 9/15/17.
//
#ifndef PROBLEM109_SOLUTION_HPP
#define PROBLEM109_SOLUTION_HPP
// 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 *sortedListToBST(ListNode *head)
{
return sortedListToBST(head, nullptr);
}
private:
TreeNode *sortedListToBST(ListNode *head, ListNode *tail)
{
// std::cout << "Head:";
//
// if(head == nullptr)
// {
// std::cout << "NULL";
// }
// else
// {
// std::cout << head->val;
// }
//
// std::cout << " Tail:";
//
// if (tail == nullptr) {
// std::cout << "NULL";
// } else
// {
// std::cout << tail->val;
// }
//
//
// std::cout << std::endl;
if(head == tail)
{
return nullptr;
}
if(head->next == tail)
{
return new TreeNode(head->val);
}
// Use fast-slow pointer to find the middle point.
ListNode* mid = head, *twiceSpeed = head;
while(twiceSpeed->next != tail)
{
if(twiceSpeed->next->next != tail)
{
mid = mid->next;
twiceSpeed = twiceSpeed->next->next;
}
else
{
twiceSpeed = twiceSpeed->next;
}
}
// std::cout << "Find mid:" << mid->val << std::endl;
TreeNode* root = new TreeNode(mid->val);
root->left = sortedListToBST(head, mid);
root->right = sortedListToBST(mid->next, tail);
return root;
}
};
#endif //PROBLEM109_SOLUTION_HPP