|
250.Given a singly linked list sorted in ascending order, convert it to a height balanced BST from this.
Microsoft Interview Questions and Answers
(Continued from previous question...)
250.Given a singly linked list sorted in ascending order, convert it to a height balanced BST from this.
Question:
Given a singly linked list sorted in ascending order, convert it to a height balanced BST from this.
maybe an answer:
template <class T>
struct SListNode
{
SListNode(T d)
: data(d), next(NULL) {}
T data;
SListNode<T> * next;
};
template <class T>
struct BTreeNode
{
BTreeNode(T d)
: data(d), left(NULL), right(NULL) {}
T data;
BTreeNode<T> * left;
BTreeNode<T> * right;
};
template <class T>
BTreeNode<T> ** ConstructArray(
SListNode<T> * first, size_t & N)
{
N = 0;
SListNode * node = first;
while (node)
{
++N;
node = node->next;
}
BTreeNode<T> ** array =
new BTreeNode<T> * [N];
node = first;
for (size_t i = 0; i < N; ++i)
{
array[i] = new BTreeNode<T>(node->data);
node = node->next;
}
return array;
}
template <class T>
BTreeNode<T> * ConstructBTree(
BTreeNode<T> ** array, size_t N)
{
if (!N) return NULL;
if (N == 1) return array[0];
size_t middle = N >> 1;
BTreeNode<T> * root = array[middle];
root->left = ConstructBTree(array, middle);
root->right = ConstructBTree(
array + middle + 1, N - middle - 1);
return root;
}
template >class T>
BTreeNode>T> * ConstructBTree(
SListNode>T> * first)
{
size_t N = 0;
BTreeNode>T> ** array =
ConstructArray(first, N);
BTreeNode>T> * root =
ConstructBTree(array, N);
delete [] array;
return root;
}
(Continued on next question...)
Other Interview Questions
| 