剑指offer-二叉搜索树与双向链表

题目描述

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

解题思路

问题是将二叉搜索树转换成一个排序的双向链表，考虑到二叉搜索树的中序遍历序列为排序序列，所以可用中序遍历的递归做法来调整指针。在遍历过程中，调整指针pLast使其指向当前已转换好双向链表的末尾也就是最大数字，这样每当遍历到一个节点，只需要调整两次指针：

1. 调整当前结点的left指针指向pLast
2. 调整pLast指向结点的right指针指向当前结点

这样递归调整完成后，pLast指向的就是双向链表的最后一个节点，要返回的是头结点，所以依次向前调整pLast直至其左指针为空即指向头结点。

代码

/*
 struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
     TreeNode(int x) :
             val(x), left(NULL), right(NULL) {
     }
 };*/
 class Solution {
 public:
     TreeNode* pLast=NULL;
     TreeNode* Convert(TreeNode* pRoot)
     {
         if(!pRoot)
             return NULL;
         ToList(pRoot);
         while(pLast->left)
             pLast=pLast->left;
         return pLast;
     }
     void ToList(TreeNode* pRoot){
         if(pRoot){
             if(pRoot->left)
                 ToList(pRoot->left);
             if(pLast){
                 pLast->right=pRoot;
                 pRoot->left=pLast;
             }
             pLast=pRoot;
             if(pRoot->right)
                 ToList(pRoot->right);
         }
     }
 };