输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。


二叉搜索树的中序遍历即是有序的，中序遍历同时转变即可，

转换左子树，左子树最右边，为左子树有序的最后一个节点为lastnode，

root->left=lastnode

如果lastnode非空，lastnode->right=root;

右树非空，转换之。


最后，原根节点指向的是序列中间，需要返回链表头，可以往前遍历即可。


void ConvertCore(TreeNode *root,TreeNode *&lastnode){

if(root==NULL)

return;

if(root->left)

ConvertCore(root->left,lastnode);

root->left=lastnode;

if(lastnode!=NULL)

lastnode->right=root;

lastnode=root;

if(root->right)

ConvertCore(root->right,lastnode);

}

TreeNode* Convert(TreeNode* pRootOfTree)

{

if(pRootOfTree==NULL)

return NULL;

TreeNode *lastnode=NULL;

ConvertCore(pRootOfTree,lastnode);

while(lastnode->left){

lastnode=lastnode->left;

}

return lastnode;

}