​LeetCode刷题实战426：将二叉搜索树转化为排序的双向链表

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 将二叉搜索树转化为排序的双向链表，我们先来看题面：

https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

Let's take the following BST as an example, it may help you understand the problem better:

将一个二叉搜索树就地转化为一个已排序的双向循环链表。可以将左右孩子指针作为双向循环链表的前驱和后继指针。

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

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.

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

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

Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

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

下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

解题

解题思路：

这道题目实际上也是将二叉搜索树序列化。

注意转换规则：左指针指向前继节点，右指针指向后继节点。

实际上就是中序遍历。

使用栈来帮助我们进行中序遍历。

在出栈时改变它的左指针，指向，前继节点prev；prev的右指针指向当前出栈的节点。

需要注意的是：在最后需要连接头指针和尾指针。

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        Node* cur = root;
        stack<Node*> stk;
        Node* head = NULL;
        Node* prev = NULL;
        while(cur || !stk.empty()){
            if(cur){
                stk.push(cur);
                cur = cur->left;
            }else{
                cur = stk.top();
                stk.pop();
                if(!head) head = cur;
                if(prev){
                    prev->right = cur;
                    cur->left = prev;
                }
                prev = cur;
                cur = cur->right;
            }
        }
        head->left = prev;
        prev->right = head;
        return head;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。