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

PROBLEM

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

难度 中等

MY ANSWER

递归遍历树的节点，改变节点左子树的最右儿子、右子树的最左儿子的指针构建双向链表。

/*
// 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:
    void changer(Node* node) {
        if(!node || !node->left) {
            return;
        }
        Node* tmp = node;
        if(node->left->right) {
            tmp = tmp->left;
            while(tmp->right->right) {
                tmp = tmp->right;
            }
        }
        if(tmp == node) {
            tmp->left->right = node;
        }
        else {
            tmp->right->right = node;
            node->left = tmp->right;
            tmp->right->left = tmp;
        }
    }
    void changel(Node* node) {
        if(!node || !node->right) {
            return;
        }
        Node* tmp = node;
        if(node->right->left) {
            tmp = tmp->right;
            while(tmp->left->left) {
                tmp = tmp->left;
            }
        }
        if(tmp == node) {
            tmp->right->left = node;
        }
        else {
            tmp->left->left = node;
            node->right = tmp->left;
            tmp->left->right = tmp;
        }
    }
    void recur(Node* node) {
        if(!node) {
            return;
        }
        recur(node->left);
        recur(node->right);
        changel(node);
        changer(node);
    }
    Node* treeToDoublyList(Node* root) {
        if(!root) {
            return nullptr;
        }
        Node* tmpl = root;
        Node* tmpr = root;
        recur(root);
        while(tmpl->left) {
            tmpl = tmpl->left;
        }
        while(tmpr->right) {
            tmpr = tmpr->right;
        }
        Node* head = tmpl;
        tmpl->left = tmpr;
        tmpr->right = tmpl;
        return head;
    }
};

BETTER SOLUTION

注意二叉搜索树的性质就是中序遍历为排序后的序列，所以按中序遍历的顺序递归访问节点更改指针即可。pre为前节点，cur为当前节点，中序遍历时pre一直按顺序在cur前面，因此直接更改pre的右指针和cur的左指针即可。最后改头节点与尾节点的指针使之相连。时间复杂度O(n)，空间复杂度O(n)。

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root) {
            return  nullptr;
        }
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
private:
    Node *pre = nullptr, *head = nullptr;
    void dfs(Node* cur) {
        if(!cur) {
            return;
        }
        dfs(cur->left);
        if(pre) {
            pre->right = cur;
        }
        else {
            head = cur;
        }
        cur->left = pre;
        pre = cur;
        dfs(cur->right);
    }
};

SUMMARY

注意二叉搜索树中序遍历结果为排序序列，递归中设置前指针与后指针，就按顺序访问节点。