Flatten Binary Tree to Linked List

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

For example,
Given

The flattened tree should look like:

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Analyse: The sequence of the linked list is the preorder traversal. So we can first do the preorder traversal then create a new tree.

Runtime: 12ms.

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void flatten(TreeNode* root) {
13         if(!root) return;
14         vector<TreeNode* > vec;
15         preorder(root, vec);
16         
17         TreeNode* current = root;
18         int index = 1;
19         while(index < vec.size()){
20             TreeNode* temp(vec[index]);
21             current->right = temp;
22             current->left = NULL;
23             current = temp;
24             index++;
25         }
26         return;
27     }
28     void preorder(TreeNode* root, vector<TreeNode* >& vec){
29         if(!root) return;
30         
31         vec.push_back(root);
32         preorder(root->left, vec);
33         preorder(root->right, vec);
34     }
35 };