TreeNode *lastpre = NULL;
void flatten(TreeNode *root) {
if(root==NULL)
return;
lastpre = root;
if(root>left==NULL && root>right==NULL)
return;
if(root>left==NULL) {
flatten(root>right);
return;
}
TreeNode* rNode = root>right;
root>right = root>left;
root>left = NULL;
flatten(root>right);
lastpre>right = rNode;
flatten(rNode);
}
Simplest C++ recursion solution


"lastpre = root;" is for "lastpre>right = rNode;", because this problem need preorder traversal.
TreeNode* rNode = root>right;
root>right = root>left;
root>left = NULL;
the code above mean put left tree to right tree for preorder traversal when the left tree is not null.And then ,flatten(root>right); first deal with the new right tree ,the old left tree,
next , lastpre>right = rNode; put old right tree to the new right tree's end,
finally , flatten(rNode); deal with old right tree.
