通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

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

75人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/915

声明:请尊重原作者的劳动,如需转载请注明出处


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

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

为了让您更好地理解问题,以下面的二叉搜索树为例:

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

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


难度:中等;标签:分治算法;编程语言:C++


我的解法

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    // c++改写
    Node* treeToDoublyList(Node* root) {
        if(root == NULL)return root;
        
        Node *head = root, *tail = root;

        if(root->left != NULL){
            Node* t = root->left;
            while(t->left != NULL){
                t = t->left;
            }
            head = t;
        }

        if(root->right != NULL){
            Node* t = root->right;
            while(t->right != NULL){
                t = t->right;
            }
            tail = t;
        }

        helper(root);
        tail->right = head;
        head->left = tail;

        return head;
    }

    void helper(Node* node){
        if(node != NULL){
            if(node->left != NULL){
                Node* t = node->left;
                while(t->right != NULL){
                    t = t->right;
                }
                helper(node->left);
                t->right = node;
                node->left = t;
            }

            if(node->right != NULL){
                Node* t = node->right;
                while(t->left != NULL){
                    t = t->left;
                }
                helper(node->right);
                t->left = node;
                node->right = t;
            }
        }
    }
};

先找到第一个head和最后一个tail结点,第一个是左边最左,最后一个是右边最右,然后helper方法完成二叉树转换成链表,对于一个结点,找到他的前趋和后继(前趋是左边最右的结点,后继是右边最左的结点),连接起来,对于它的左右结点,进行一样的操作,注意一下分治递归的写法,想清楚helper的过程,剩下的交给helper来完成就可以了


其它解法

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root) return NULL;
        Node* first=NULL;
        Node* travel=NULL;
        treeToDoublyListHelper(root,first,travel);
        first->left=travel;
        travel->right=first;
        return first;
    }
private:
    void treeToDoublyListHelper(Node* root,Node* &first,Node* &travel){
        if(!root) return;
        treeToDoublyListHelper(root->left,first,travel);
        if(first==NULL){
            first=root;
            travel=root;
        }
        else{
            travel->right=root;
            root->left=travel;
            travel=root;
        }
        treeToDoublyListHelper(root->right,first,travel);
    }
};

有点绕人,treeToDoublyListHelper的处理顺序是先左,再当前,再右,相当于中序遍历,对当前处理时,最后travel=root,结合中序遍历,也就是说处理完left时,travel正好是前趋,所以与前趋连接,这样不断前连,就能成为一个完整的双向链表,最后还将首尾连接起来


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告