在不创建任何新节点的条件下将二叉查找树转换为排序的双向链表。

二叉查找树

solution_1

二叉查找树的特点就是左子节点<根节点<右子节点所以，想办法用中序遍历调整一下指针的指向就可以了

我们有一个树的根节点，然后假设还有一个链表的尾结点（因为我们从最小的节点开始，所以是往链表的后面加新的节点）

然后，根据我们的思路，我们要从树的最底层开始往上，并且是中序遍历
树里面最常用的就是递归
因此我们先找到最底层的左子树（如果有的话）

if (root->left)
        transform(pcurrent->left,plastListNode);

这样一直到pcurrent->left->left是NULL为止，这个时候pcurrent->left是最后一个非空节点。

然后我们进行一些修改指针指向的工作：

pcurrent->left = plastListNode;

    if (plastListNode)
    {
        plastListNode->right = pcurrent;
    }
    plastListNode = pcurrent;

大家可以自己演练一下怎么指指针。。

然后在后面，由于是中序遍历，所以加上右边的就可以了

#include <iostream>

struct treeNode
{
    int data;
    treeNode* left;
    treeNode* right;
};

void transform(treeNode* root,treeNode*& plastListNode)
{
    if (!root)
        return;
    treeNode* pcurrent=root;
    if (root->left)
        transform(pcurrent->left,plastListNode);
    pcurrent->left = plastListNode;

    if (plastListNode)
    {
        plastListNode->right = pcurrent;
    }
    plastListNode = pcurrent;

    if (pcurrent->right)
        transform(pcurrent->right, plastListNode);
    
}
treeNode* solution1(treeNode* tree)
{
    treeNode* list = NULL;
    transform(tree, list);
    treeNode* headOfList = list;
    while (headOfList&&headOfList->left)//转换到表头
        headOfList = headOfList->left;
    return headOfList;
}

solution_2

第二种解法呢，和我们一般的思维比较像，分左边和右边两种情况调整指针指向。
if (tree->left) pleft = transform_2(tree->left, false); //now pleft is the last & left of tree if (pleft) { pleft->right = tree; //tree->left = pleft; }
这段代码就是先找到最左边的节点，然后让pleft的右指针指向其父节点。
其实我觉得//tree->left = pleft;这句话是不需要的，因为本来tree就是pleft的父节点，我把这行代码注释掉试了一下也是可以的。

然后后面就是同样的对最下面的右节点进行调整。

调整完了之后，为了之后的工作，我们把指针的位置调整到链表的头或者尾。
取决于我们当前调整的节点是左边的还是右边的。每次调整结束后，我们的指针总是指向父节点：

• 如果调整的是左边的，那么调整结束后，我们把指针右移到最右端，方便接着；
• 如果是右边的，我们把指针移到链表的最开始，方便打印。
  。。其实我还是没懂为啥要这样调整。（主要是递归的执行过程）

我写了一个打印的程序试了一下：

执行结果

这个还需要再理解。。

---

code：

treeNode* transform_2(treeNode* tree, bool asright)
{
    if (!tree)
        return NULL;
    treeNode* tmp=tree;
    treeNode* pleft=NULL;//what?!!!-ver3.0
    treeNode* pright=NULL;
    if (tmp->left)
        pleft = transform_2(tmp->left, false);
    //now pleft is the last & left of tree
    if (pleft)
    {
        pleft->right = tmp;
        //tree->left = pleft;
        std::cout << "connectleft" << "\n";
    }

    if (tmp->right)
        pright = transform_2(tmp->right, true);
    if (pright)
    {
        
        pright->left = tmp;
        //tree->right = pright;
        std::cout << "connectright" << "\n";
    }

    treeNode* phead = tree;
    if (asright)
    {
        while (phead->left)
            phead = phead->left;
        std::cout << "asright" << "\n";
    }
    else
    {
        while (phead->right)
        {
            phead = phead->right;
        }
        std::cout << "asleft" << "\n";
    }
    return phead;
}

文章参考何海涛大神文章