DDL's homepage

排序二叉树转化为双向链表

发表于 分类于 Valine：

问题描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

这道题目注意审题，注意双向链表的表头和表尾部是否连接，如果连接就是一个循环双向链表。

循环双向链表+递归

思路上很直接，在二叉搜索树的中序遍历基础上，改变当前节点root指针指向，因为我们需要将root->left 指向前一个顺序遍历的节点，我们用一个指针pre表示当前节点的前一个节点。

解法一
递归返回头节点和尾节点，注意递归传递的参数应该是引用类型(不然debug搞死你。。。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        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

大体和上面一样递归，但是递归的时候没有保存头节点,而是在把节点指针顺序改变好之后(实际上这个时候双链表已经建好了）通过链表的反向遍历找到头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Node*pre=NULL;
    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        dfs(root);
        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 利用栈非递归中序遍历

二叉搜索树的中序遍历后结果是一个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }