题解 | 二叉搜索树与双向链表

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
  public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
      if (pRootOfTree == nullptr) return nullptr;
        
        TreeNode* pre = nullptr;
        // 中序遍历并调整指针
        inorder(pRootOfTree, pre);
        
        // 找到链表的头节点（最左边的节点）
        TreeNode* head = pRootOfTree;
        while (head->left != nullptr) {
            head = head->left;
        }
        return head;
    }
    
private:
    void inorder(TreeNode* root, TreeNode*& pre) {
        if (root == nullptr) return;
        
        // 遍历左子树
        inorder(root->left, pre);
        
        // 处理当前节点
        // 将当前节点的左指针指向前驱节点
        root->left = pre;
        
        // 如果前驱节点存在，将前驱节点的右指针指向当前节点
        if (pre != nullptr) {
            pre->right = root;
        }
        
        // 更新前驱节点为当前节点
        pre = root;
        
        // 遍历右子树
        inorder(root->right, pre);
    }
};

思路1:已知将二叉搜索树进行中序遍历可以得到由小到大的顺序排列，因此本题最直接的想法就是进行中序遍历。
将中序遍历的结果用数组存储下来，得到的数组是有从小到大顺序的。最后将数组中的结点依次连接即可。
思路2:二叉搜索树的中序遍历是有序的，所以我们需要利用中序遍历来调整指针指向。关键是在遍历过程中维护一个前驱节点，将当前节点与前驱节点连接起来。
二叉搜索树转换成一个排序的双向链表的思路都离不开中序遍历,两个思路的差别是时间复杂度不同