在不創(chuàng)建任何新節(jié)點的條件下將二叉查找樹轉(zhuǎn)換為排序的雙向鏈表鳖孤。
solution_1
二叉查找樹的特點就是左子節(jié)點<根節(jié)點<右子節(jié)點所以朗若，想辦法用中序遍歷調(diào)整一下指針的指向就可以了
我們有一個樹的根節(jié)點趾牧，然后假設(shè)還有一個鏈表的尾結(jié)點（因為我們從最小的節(jié)點開始愧哟，所以是往鏈表的后面加新的節(jié)點）
然后褪贵，根據(jù)我們的思路匣摘，我們要從樹的最底層開始往上亏吝，并且是中序遍歷
樹里面最常用的就是遞歸
因此我們先找到最底層的左子樹（如果有的話）
if (root->left)
transform(pcurrent->left,plastListNode);
這樣一直到pcurrent->left->left是NULL為止岭埠，這個時候pcurrent->left是最后一個非空節(jié)點。
然后我們進(jìn)行一些修改指針指向的工作：
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)//轉(zhuǎn)換到表頭
headOfList = headOfList->left;
return headOfList;
}
solution_2
第二種解法呢馆类，和我們一般的思維比較像混聊，分左邊和右邊兩種情況調(diào)整指針指向。
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; }
這段代碼就是先找到最左邊的節(jié)點乾巧，然后讓pleft的右指針指向其父節(jié)點句喜。
其實我覺得//tree->left = pleft;這句話是不需要的，因為本來tree就是pleft的父節(jié)點卧抗，我把這行代碼注釋掉試了一下也是可以的藤滥。
然后后面就是同樣的對最下面的右節(jié)點進(jìn)行調(diào)整。
調(diào)整完了之后社裆，為了之后的工作拙绊，我們把指針的位置調(diào)整到鏈表的頭或者尾。
取決于我們當(dāng)前調(diào)整的節(jié)點是左邊的還是右邊的泳秀。每次調(diào)整結(jié)束后标沪，我們的指針總是指向父節(jié)點：
- 如果調(diào)整的是左邊的，那么調(diào)整結(jié)束后嗜傅，我們把指針右移到最右端金句，方便接著；
- 如果是右邊的吕嘀，我們把指針移到鏈表的最開始违寞，方便打印。
偶房。趁曼。其實我還是沒懂為啥要這樣調(diào)整。（主要是遞歸的執(zhí)行過程）
我寫了一個打印的程序試了一下：
這個還需要再理解棕洋。挡闰。
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;
}
文章參考何海濤大神文章
