题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
二叉树的定义如下：
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
};
思路：
在二叉树中，每个结点都有两个指向子结点的指针，在双向链表中，每个结点也有两个指针，他们分别指向前一个结点和后一个结点。两种数据结构看起来很相似，是可以通过某种方式将二叉搜索树转换为排序的双向链表。
在二叉搜索树中，当遍历到根结点时，把二叉树看成三部分，根结点、左子树和右子树，根据排序链表的定义，根结点的左指针应该指向左子树中最大的结点，即最右边的结点；根结点的右指针应该指向右子树中最小的结点，即最左边的结点。
在把左子树、右子树都转换成排序的双向排序链表（递归）之后，再跟根结点连接起来，整棵二叉搜索树就转换成了排序的双向链表。
因此在设计递归函数时，需要返回链表的头指针和尾指针，并改变当前结点的左右指针的指向。（详见代码）
代码：
#include <iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
};
TreeNode* ConvertNodes(TreeNode* pRoot,TreeNode** pTail);
TreeNode* Convert(TreeNode* pRoot){
TreeNode* pTail=NULL;
return ConvertNodes(pRoot,&pTail);
}
TreeNode* ConvertNodes(TreeNode* pRoot,TreeNode** pTail){
if(pRoot==NULL)
return NULL;
if(pRoot->left==NULL && pRoot->right==NULL){
*pTail=pRoot;
return pRoot;
}
TreeNode* leftHead=pRoot;
if(pRoot->left!=NULL){
leftHead=ConvertNodes(pRoot->left,pTail);
pRoot->left=*pTail;
if(*pTail!=NULL)
(*pTail)->right=pRoot;
*pTail=pRoot;
}
if(pRoot->right!=NULL){
TreeNode* rightHead=ConvertNodes(pRoot->right,pTail);
pRoot->right=rightHead;
if(rightHead!=NULL)
rightHead->left=pRoot;
}
return leftHead;
}
在线测试OJ：
http://www.nowcoder.com/books/coding-interviews/947f6eb80d944a84850b0538bf0ec3a5?rp=2
AC代码:
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* pTail=NULL;
return ConvertNodes(pRootOfTree,&pTail);
}
TreeNode* ConvertNodes(TreeNode* pRoot,TreeNode** pTail){
if(pRoot==NULL)
return NULL;
if(pRoot->left==NULL && pRoot->right==NULL){
*pTail=pRoot;
return pRoot;
}
TreeNode* leftHead=pRoot;
if(pRoot->left!=NULL){
leftHead=ConvertNodes(pRoot->left,pTail);
pRoot->left=*pTail;
if(*pTail!=NULL)
(*pTail)->right=pRoot;
*pTail=pRoot;
}
if(pRoot->right!=NULL){
TreeNode* rightHead=ConvertNodes(pRoot->right,pTail);
pRoot->right=rightHead;
if(rightHead!=NULL)
rightHead->left=pRoot;
}
return leftHead;
}
};