排序二叉樹轉(zhuǎn)化為雙向鏈表
問題描述：
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的循環(huán)雙向鏈表凉蜂。要求不能創(chuàng)建任何新的節(jié)點(diǎn)擅笔，只能調(diào)整樹中節(jié)點(diǎn)指針的指向。
這道題目注意審題岳服，注意雙向鏈表的表頭和表尾部是否連接，如果連接就是一個(gè)循環(huán)雙向鏈表蜕煌。
循環(huán)雙向鏈表+遞歸
思路上很直接派阱，在二叉搜索樹的中序遍歷基礎(chǔ)上，改變當(dāng)前節(jié)點(diǎn)root指針指向斜纪，因?yàn)槲覀冃枰獙?code>root->left 指向前一個(gè)順序遍歷的節(jié)點(diǎn)，我們用一個(gè)指針pre表示當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)文兑。
解法一
遞歸返回頭節(jié)點(diǎn)和尾節(jié)點(diǎn)盒刚，注意遞歸傳遞的參數(shù)應(yīng)該是引用類型(不然debug搞死你。绿贞。因块。)
Node* treeToDoublyList(Node* root) {
if(!root) return root; //特判空節(jié)點(diǎn)
Node*head=nullptr,*pre=nullptr;
dfs(root,head,pre);
head->left=pre;
pre->right=head;
return head;
}
void dfs(Node*root,Node*&head,Node*&pre){
if(!root) return ;
dfs(root->left,head,pre);
//cout<<root->val<<endl;
if(!head){
head=root;
pre=root;
}
else{
pre->right=root;
root->left=pre;
pre=root;
}
dfs(root->right,head,pre);
}
解法2
大體和上面一樣遞歸，但是遞歸的時(shí)候沒有保存頭節(jié)點(diǎn),而是在把節(jié)點(diǎn)指針順序改變好之后(實(shí)際上這個(gè)時(shí)候雙鏈表已經(jīng)建好了）通過鏈表的反向遍歷找到頭節(jié)點(diǎn)
Node*pre=NULL;
Node* treeToDoublyList(Node* root) {
if(!root) return root;
dfs(root);
//反向遍歷尋找頭節(jié)點(diǎn)
auto head=pre;
while(head&&head->left) head=head->left;
head->left=pre;
pre->right=head;
return head;
}
void dfs(Node*root){
if(!root) return ;
dfs(root->left);
root->left=pre;
if(pre) pre->right=root;
pre=root;
dfs(root->right);
}
解法3 利用棧非遞歸中序遍歷
中序的非遞歸遍歷經(jīng)常用到籍铁，因?yàn)槎嫠阉鳂涞闹行虮闅v后結(jié)果是一個(gè)有序
Node* treeToDoublyList(Node* root) {
if(!root) return root;
stack<Node*> stk;
Node*pre=NULL,*head=NULL;
while(root||stk.size()){
while(root){
stk.push(root);
root=root->left;
}
root=stk.top();
stk.pop();
root->left=pre;
if(pre) pre->right=root;
pre=root;
root=root->right;
}
head=pre;
while(head&&head->left) head=head->left;
head->left=pre;
pre->right=head;
return head;
}
