剑指offer面试题36---二叉搜索树与双向链表

1.题目描述：

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

2.通过书上一个例子的图形象描述下：

 

3.代码实现

//一开始我想到的是：中序遍历然后把节点依次用左右指针连起来即可，没有象书中讲的那么麻烦的方法 ，不过书中的这种递//  //归的方法还是值得练习的

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <vector>

class Solution {
public:
    vector<TreeNode*> Vec;//思路是：中序遍历pRootOfTree，且把每次访问的节点放入Vec数组，最后把Vec中元素用双向指针连起来
    void Midorder(TreeNode* pRootOfTree)//这个函数实现中序遍历并把节点按顺序放入Vec
    {
         if(pRootOfTree==nullptr)
              return;
        
         else
         {
              Midorder(pRootOfTree->left);
              Vec.push_back(pRootOfTree);
              Midorder(pRootOfTree->right);
         }
    }
    
    
    
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr)
            return nullptr;
        Midorder(pRootOfTree);
        vector<TreeNode*>::iterator cur;
    for(cur=Vec.begin();cur!=Vec.end();++cur)
    {
        if(cur==(Vec.end()-1))
            break;
        
         (*cur)->right=(*(cur+1));
        (*(cur+1))->left=(*cur);
    }
    
        return Vec[0];
    }
};