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.
void flatten(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root==NULL) return;
if(root->left == NULL && root->right == NULL) return;
flatten(root->left);
flatten(root->right);
TreeNode* tmpright = root->right;
root->right = root->left;
root->left = NULL;
TreeNode* tmp = root;
while(tmp->right)
tmp = tmp->right;
tmp->right = tmpright;
return;
}