flattern BT to right linklist
这种属于两种DS之间的转换，一开始没想到就地的方法，但是先序遍历一遍，然后边尾插法建立linklist，但是这样不是就地的。
后来想想先序要一直往左走，所以边改右孩子可能会丢失右孩子，如果暂时记住，后面还不知道有多少个right需要先record想了一下，没有好的方法，思路终结。
后来想，可以先left建立，然后转成right么？这样是不会丢失先序遍历的结构的，所以按照这个思路写算法。AC了，后来发现还要记得把left置为NULL。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode *root) {
stack<TreeNode*> S;
TreeNode* p=root, *lastp=NULL;
while(!S.empty()||p!=NULL)
{
while(p!=NULL)
{
if(lastp!=NULL)
lastp->left=p;
//if(lastp!=root)
lastp=p;
S.push(p);
p=p->left;
}
p=S.top();
S.pop();
p=p->right;
}
p=root;
while(p!=NULL)
p->right=p->left,p->left=NULL,p=p->right;
}
};