將排序二叉樹(shù)轉(zhuǎn)化成雙向鏈表，應(yīng)該是一道很常見(jiàn)的面試題目，網(wǎng)上的實(shí)現(xiàn)比較多，有用遞歸也有用中序遍歷法的。看到一位外國(guó)友人的實(shí)現(xiàn)，還是比較清晰的，思路如下：
1，如果左子樹(shù)不為null，處理左子樹(shù)
1.a）遞歸轉(zhuǎn)化左子樹(shù)為雙向鏈表；
1.b）找出根結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)（是左子樹(shù)的最右的節(jié)點(diǎn)）
1.c）將上一步找出的節(jié)點(diǎn)和根結(jié)點(diǎn)連接起來(lái)
2，如果右子樹(shù)不為null，處理右子樹(shù)（和上面的很類似）
1.a）遞歸轉(zhuǎn)化右子樹(shù)為雙向鏈表；
1.b）找出根結(jié)點(diǎn)的后繼節(jié)點(diǎn)（是右子樹(shù)的最左的節(jié)點(diǎn)）
1.c）將上一步找出的節(jié)點(diǎn)和根結(jié)點(diǎn)連接起來(lái)
3，找到最左邊的節(jié)點(diǎn)并返回
附上國(guó)外友人的鏈接：http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
下面是代碼實(shí)現(xiàn)：
bintree2listUtil函數(shù)返回的node＊ 是root節(jié)點(diǎn)，bintree2list函數(shù)返回的是頭節(jié)點(diǎn)
node* bintree2listUtil(node* root)
{
if (root == NULL)
return root;
if (root->left != NULL)
{
node* left = bintree2listUtil(root->left);
for (; left->right!=NULL; left=left->right);
left->right = root;
root->left = left;
}
if (root->right!=NULL)
{
node* right = bintree2listUtil(root->right);
for (; right->left!=NULL; right = right->left);
right->left = root;
root->right = right;
}
return root;
}
node* bintree2list(node *root)
{
if (root == NULL)
return root;
root = bintree2listUtil(root);
while (root->left != NULL)
root = root->left;
return (root);