笔试刷题-头条2018-05-31

题目描述

/** 
题目描述 
以下函数用于将一颗二叉搜索树转换成一个有序的双向链表。 
要求不能创建任何新的节点，只能调整树种节点指针的指向。 
 
如输入下图中左边的二叉搜索树，则输出转换后的排序双向链表： 
 
      10 
 
    /      \ 
 
   6      14 
 
  /  \      /  \ 
 
4   8  12  16 
 
转换成： 
 
 4 <=> 6 <=> 8 <=> 10 <=> 12  <=> 14 <=> 16 
 
*/   

思路如下：
采用的是bfs的思想，从root开始，然后依次放入其lch rch分别处理指针，由于要标记什么节点已经处理过了，但是这里可以不用，由于原来是树没有环，但是双向链表是有环的图，所以可以通过如此判断有无换然后判断什么指针已经处理过了，然后采用bfs遍历一遍树，同时修改指针即可。若一个当前的node->left=node->left->right形成换，那么node->left不用再被处理了

转化代码如下：

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;  
    //重构  
    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)){  
            //先入队列  
            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)){  
            //先入队列  
            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;
}