26：二叉搜索树与双向链表

题目描述

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

解题思路

• 二叉搜索树的中序即使有序，中序递归，记录前驱结点。
• 二叉搜索树最左边的即为最小值，可以作为链表的头结点。

AC代码

class Solution {
public:
    
    void mid(TreeNode* cur, TreeNode*& pre)
    {
       if(!cur)
           return;
        
        mid(cur->left, pre);
        
        cur->left = pre;
        if(pre)
            pre->right = cur;
        pre = cur;
        
        mid(cur->right, pre);
    }

    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == NULL)
            return NULL;
        TreeNode* pre = NULL;
        mid(pRootOfTree, pre);
        
        TreeNode* res = pRootOfTree;
        
        while(res->left)
            res = res->left;
       return res;
        
    }