題目描述

/** 
題目描述 
以下函數(shù)用于將一顆二叉搜索樹轉(zhuǎn)換成一個(gè)有序的雙向鏈表。 
要求不能創(chuàng)建任何新的節(jié)點(diǎn)褪子，只能調(diào)整樹種節(jié)點(diǎn)指針的指向辙售。 
 
如輸入下圖中左邊的二叉搜索樹轻抱，則輸出轉(zhuǎn)換后的排序雙向鏈表： 
 
      10 
 
    /      \ 
 
   6      14 
 
  /  \      /  \ 
 
4   8  12  16 
 
轉(zhuǎn)換成： 
 
 4 <=> 6 <=> 8 <=> 10 <=> 12  <=> 14 <=> 16 
 
*/   

思路如下：
采用的是bfs的思想，從root開始圾亏，然后依次放入其lch rch分別處理指針十拣，由于要標(biāo)記什么節(jié)點(diǎn)已經(jīng)處理過了，但是這里可以不用志鹃，由于原來是樹沒有環(huán)夭问，但是雙向鏈表是有環(huán)的圖，所以可以通過如此判斷有無換然后判斷什么指針已經(jīng)處理過了曹铃，然后采用bfs遍歷一遍樹缰趋，同時(shí)修改指針即可。若一個(gè)當(dāng)前的node->left=node->left->right形成換陕见，那么node->left不用再被處理了

轉(zhuǎn)化代碼如下：

struct Node{  
    int val=-1;  
    Node *left=NULL;  
    Node *right=NULL;  
    Node(){}  
    Node(int val){  
        this->val = val;  
        this->left = NULL;  
        this->right = NULL;  
    }  
};  
Node *Convert(Node *root){  
    if(root==NULL)  
        return root;  
    Node *listHead = root;  
    while(listHead->left!=NULL)  
        listHead = listHead->left;  
    //重構(gòu)  
    queue<Node*> que;  
    que.push(root);  
    set<Node*> marked;  
    while(!que.empty()){  
        Node *cur = que.front();  
        que.pop();  
        if(cur->left && (cur->left->right!=cur)){  
            //先入隊(duì)列  
            que.push(cur->left);  
            Node *curLeft = cur->left;  
            while(curLeft->right)  
                curLeft = curLeft->right;  
            //改動指針  
            cur->left = curLeft;  
            curLeft->right = cur;  
        }  
        if(cur->right && (cur->right->left!=cur)){  
            //先入隊(duì)列  
            que.push(cur->right);  
            Node *curRight = cur->right;  
            while(curRight->left)  
                curRight = curRight->left;  
            //改動指針  
            cur->right = curRight;  
            curRight->left = cur;  
        }  
    }  
    return listHead;  
}  

測試題目例子代碼：

int main(){
    Node *n1 = new Node(10);
    Node *n2 = new Node(6);
    Node *n3 = new Node(14);
    Node *n4 = new Node(4);
    Node *n5 = new Node(8);
    Node *n6 = new Node(12);
    Node *n7 = new Node(16);
    n1->left = n2;
    n1->right = n3;
    n2->left = n4;
    n2->right = n5;
    n3->left = n6;
    n3->right = n7;
    Node *listHead = Convert(n1);
    Node *reversedListHead;
    Node *cur = listHead;
    while(cur){
        printf("%d ", cur->val);
        if(!cur->right)
            reversedListHead = cur;
        cur = cur->right;
    }
    printf("\n");
    cur = reversedListHead;
    while(cur){
        printf("%d ", cur->val);
        cur = cur->left;
    }
    return 0;
}