# Build BST from sorted array and Linked List

Q:Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Q:Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

It’s more efficient to build a sorted array fist and use that array to build the BST. This require O(n) space and O(n) time.

Q:Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

1.fine the parent of the node after which the list needed to be reversed, if necessary
2.reverse the nodes needed to be reversed
3.reconnect the fist half of the original list with the new head of the reversed list, if necessary;
reconnect the end of the reversed list with the rest of the list. # Reorder List

Q：Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

1. find the end of the new list;
2. push the rest of the nodes into stack;
3. pop and merge nodes into the list;
(When dealing with linkedlist, always remember to break the link when necessary!!) 1. find the end of the new list and break the original list into two halves according to that node;
2. reverse the second list;
3. merge two lists; Pictures from here. A great place!

# Pascal’s Triangle

Q:Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
,
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

Q2:Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

# Flatten Binary Tree to Linked List

Q:Given a binary tree, flatten it to a linked list in-place.

For example,
Given

1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Hints:
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

# Binary Tree Level Order Traversal

Q:Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree `{3,9,20,#,#,15,7}`,

```    3
/ \
9  20
/  \
15   7```

return its level order traversal as:

```[
,
[9,20],
[15,7]
]``` V2: Bottom-up.
Q:Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
,
]

The only thing changed is line 33. # combination

Q：Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

# Permutation

Q:

Given a collection of numbers, return all possible permutations.

For example,
`[1,2,3]` have the following permutations:
`[1,2,3]``[1,3,2]``[2,1,3]``[2,3,1]``[3,1,2]`, and `[3,2,1]`. Version 2: with duplicates.

Q:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
`[1,1,2]` have the following unique permutations:
`[1,1,2]``[1,2,1]`, and `[2,1,1]`. V1-Just print it out:

```public void main(String[] arg){
char[] a ={'a','b','c'};
perm(a,0,a.length-1);
}

public void perm(char[] a, int k, int n){
if(k==n){//print
System.out.println("");
for(int i = 0; i<a.length;i++)	System.out.print(a[i]);
}else{
for(int i = k; i<=n;i++){
//swap a[k] and a[i]
char p = a[k];a[k]=a[i];a[i]=p;
perm(a,k+1,n);
//swap back a[k] and a[i]
char g = a[k];a[k]=a[i];a[i]=g;
}
}
}
```

# Return the String of a number’s binary representation

Q:Given a number, return the String of it’s binary representation

This function only work for positive integer!

```String decToBin(int n){
if(n==0) return new String("0");
StringBuilder r=new StringBuilder();
while(n!=0){
//get bit
if((n&(1<<0))==0) r.insert(0, "0");
else r.insert(0,"1");
n=n>>>1;
}
return r.toString();
//or you could use r.append() in above
//and use r.reverse().toString(); in here
}
```

# List Flattening and List Unflattening

Q:PIE P:53

These function haven’t been tested yet.
List Flattening:

```void flattenList(Node head,Node tail){
Node childTail;
//childTail is used for finding the tail of the child

/**Traverse through the list **/
while(curr.next!=null){
/**Find child**/
if(curr.child!=null){
/**After found a child,
//1)link the child to the tail
//2)find the tail of the child's list
//3)update tail**/

/**1)link the child to the tail**/
tail.next=curr.child;
curr.child.prev=tail;

/**2)find the tail of the child's list**/
childTail=curr.child;
while(childTail.next!=null){
childTail=childTail.next;
}

/**3)update tail**/
tail=childTail;
}
curr=curr.next;
}
}
```

List Unflatterning:

```void unflattenList(Node head, Node tail){

/**Traverse through the list 1st time & breaking the prev link of child;
//the breaking prev link is a mark of a child**/
while(curr.next!=null){
/**Find a child**/
if(curr.child!=null){
curr.child.prev=null;
}
curr=curr.next;
}

/**Traverse through the list 1st time & breaking the next link which links to a child**/
while(curr.next!=null){
/**Find a child**/
if(curr.prev==null){
prevNode.next=null;
}
prevNode=curr;
curr=curr.next;
}

/**Update the tail**/
while(curr.next!=null){
curr=curr.next;
}
tail=curr;
}
```

List Unflattening, using recursion.
/*
* Algorithm:
* Explore path:
* While not at the end
* If current node has a child
* Separate the child from its previous node
* Explore path beginning with the child
* Go onto the next node
*/

```

/**Update the tail**/
while(curr.next!=null){
curr=curr.next;
}
tail=curr;
}

while(curr.next!=null){
next=curr.next;
/**Find a child**/
if(curr.child!=null){
Node child = curr.child;