转载

【剑指offer】面试题27：二叉搜索树与双向链表

题目：

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

思路：

假设已经处理了一部分（转换了左子树），则得到一个有序的双向链表，现在则需要将根结点和链表的尾结点链接，然后再转换右子树。

这样分为三步：

1.转换左子树；

2.链接根节点。设置根节点的左指针、尾结点的右指针。更新尾结点。

3.转换右子树。

代码：

/* struct TreeNode {  int val;  struct TreeNode *left;  struct TreeNode *right;  TreeNode(int x) :    val(x), left(NULL), right(NULL) {  } };*/ class Solution { public:  TreeNode* Convert(TreeNode* pRootOfTree)  {   if(pRootOfTree==NULL)  return NULL;   TreeNode *pLastNodeInList=NULL;   ConvertNode(pRootOfTree,pLastNodeInList);   TreeNode *pHead=pLastNodeInList;//找到头结点   while(pHead!=NULL && pHead->left!=NULL)    pHead=pHead->left;   return pHead;  } private:  void ConvertNode(TreeNode *pCurrent, TreeNode* &pLastNodeInList)  {   if(pCurrent==NULL)  return ;   if(pCurrent->left!=NULL)//转换左子树    ConvertNode(pCurrent->left,pLastNodeInList);   pCurrent->left=pLastNodeInList;//链接根结点  设置根节点的左指针、尾结点的右指针   if(pLastNodeInList!=NULL)   {    pLastNodeInList->right=pCurrent;   }   pLastNodeInList=pCurrent;//更新尾结点      ConvertNode(pCurrent->right,pLastNodeInList);//转换右子树  } };