-
Notifications
You must be signed in to change notification settings - Fork 0
/
BST1-BST to LL
71 lines (64 loc) · 2.21 KB
/
BST1-BST to LL
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
Given a BST, convert it into a sorted linked list. You have to return the head of LL.
Input format:
The first and only line of input contains data of the nodes of the tree in level order form. The data of the nodes of the tree is separated by space. If any node does not have left or right child, take -1 in its place. Since -1 is used as an indication whether the left or right nodes exist, therefore, it will not be a part of the data of any node.
Output Format:
The first and only line of output prints the elements of sorted linked list.
Constraints:
Time Limit: 1 second
Sample Input 1:
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
Sample Output 1:
2 5 6 7 8 10
*********************************Solution********************************
class QueueUsing<T>
{
T head;
T tail;
}
public class Solution {
public static LinkedListNode<Integer> constructLinkedList(BinaryTreeNode<Integer> root) {
QueueUsing<LinkedListNode<Integer>> queueNode=constructHelper(root);
return queueNode.head;
}
public static QueueUsing<LinkedListNode<Integer>> constructHelper(BinaryTreeNode<Integer> root)
{
if(root==null)
return new QueueUsing<LinkedListNode<Integer>>();
if(root.left==null && root.right==null)
{
QueueUsing<LinkedListNode<Integer>> queueNode= new QueueUsing<LinkedListNode<Integer>>();
queueNode.head=new LinkedListNode<Integer>(root.data);
queueNode.tail=null;
return queueNode;
}
QueueUsing<LinkedListNode<Integer>> queueNodeLeft= constructHelper(root.left);
QueueUsing<LinkedListNode<Integer>> queueNodeRight=constructHelper(root.right);
QueueUsing<LinkedListNode<Integer>> queueNode= new QueueUsing<LinkedListNode<Integer>>();
LinkedListNode<Integer> newNode= new LinkedListNode<Integer>(root.data);
if(queueNodeLeft.head==null)
{
queueNode.head=newNode;
}
else
{
queueNode.head=queueNodeLeft.head;
}
if(queueNodeLeft.tail==null)
{
queueNode.head.next=newNode;
queueNode.tail=newNode;
}
else{
queueNodeLeft.tail.next=newNode;
queueNode.tail=newNode;
}
if(queueNodeRight.head!=null)
{
queueNode.tail.next=queueNodeRight.head;
queueNode.tail=queueNodeRight.head;
}
if(queueNodeRight.tail!=null)
queueNode.tail=queueNodeRight.tail;
return queueNode;
}
}