在不创建任何新节点的条件下将二叉查找树转换为排序的双向链表。
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;
}
文章参考何海涛大神文章
