signed

QiShunwang

“诚信为本、客户至上”

剑指 Offer 36. 二叉搜索树与双向链表

2020/8/19 21:49:55   来源:

剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:在这里插入图片描述

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

在这里插入图片描述
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

//左有序链表最大值节点 + root + 右有序链表最小值节点
//left前驱 right后继
//再使左有序链表头结点的前驱指向右有序链表最大值节点的,右有序链表的最大值节点的后继指向使左有序链表头结点
class Solution {
public:
    Node* treeToDoublyList(Node* root) {

        if(root == NULL) return NULL;

        Node* left_head = treeToDoublyList(root->left);
        Node* right_head = treeToDoublyList(root->right);
        Node* left_end;
        Node* right_end;

        if(left_head == NULL && right_head == NULL)
        {
            root->left = root;
            root->right = root;
            return root;
        }
        else if(left_head == NULL)
        {
            right_end = right_head->left;
            right_head->left = root;
            right_end->right = root;
            root->left = right_end;
            root->right = right_head;
            return root;
        }
        else if(right_head == NULL)
        {
            left_end = left_head->left;
            left_end->right = root;
            left_head->left = root;
            root->right = left_head;
            root->left = left_end;
            return left_head;
        }
        left_end = left_head->left;
        right_end = right_head->left;

        left_end->right = root;
        root->left = left_end;
        right_head->left = root;
        root->right = right_head;

        left_head->left = right_end;
        right_end->right = left_head;
        return left_head;
    }
};