【刷题】P187剑指offer:面试题36:二叉搜索树与双向链表

  • 时间:
  • 浏览:
  • 来源:互联网

面试题36:二叉搜索树与双向链表
输入一棵二叉搜索树,将该二又搜索树转换成一个排序的双向 链表。
要求不能创建任何新的节点,只能调整树中节点指针的指向。

力扣链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/submissions/

class Solution
{
public:
    Node* copyRandomList(Node* head)
    {
        if(head==NULL)
            return NULL;
        CloneNodes(head);
        ConnectSiblingNodes(head);
        return ReconnestNodes(head);
    }

    void CloneNodes(Node* head)
    {
        if(head==NULL)
            return;
        Node* node = head;
        while(node)
        {
            Node* cnode = new Node(node->val);
            cnode->next = node->next;
            node->next = cnode;
            node = cnode->next;
        }
    }

    void ConnectSiblingNodes(Node* head)
    {
        if(head==NULL)
            return;
        Node* node = head;
        while(node)
        {   
            Node* cnode = node->next;
            if(node->random)
            {
                cnode->random = node->random->next;
            }
            node = cnode->next;
        }
    }

    Node* ReconnestNodes(Node* head)
    {
        if(head==NULL)
            return NULL;
        Node* node = head;
        Node* cnode = NULL;
        Node* chead = NULL;
        if(node)
        {
            cnode=chead=node->next;
            node->next=cnode->next;
            node=node->next;
        }

        while(node)
        {
            cnode->next = node->next;
            cnode = cnode->next;
            node->next = cnode->next;
            node = node->next;
        }

        return chead;
    }
};

本文链接http://www.dzjqx.cn/news/show-617030.html