面试题 36：二叉搜索树和双向链表.md

试题链接：49. 二叉搜索树与双向链表 - AcWing题库

方法一：中序遍历

• 思路：要得到排序双向链表就可以联想到二叉搜索树中序遍历的结果就是有序的，要将原二叉树构造为双向链表可以递归的将左子树和右子树构造好，然后和当前节点再连接起来，但是对于当前节点来说，不知道是左子树还是右子树，因此就无法判断节点是连接到头部还是尾部，只有父节点知道，因此返回值需要包含双向链表的头部和尾部，然后由父节点进行连接操作。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    TreeNode* convert(TreeNode* root) {
        return dfs(root).first;
    }
    
    pair<TreeNode*, TreeNode*> dfs(TreeNode* root) {
        if (!root) return {nullptr, nullptr};
        
        auto [lh, lt] = dfs(root->left);
        if (lt) {
            root->left = lt;
            lt->right = root;
        }
        else lh = root;
        auto [rh, rt] = dfs(root->right);
        if (rh) {
            root->right = rh;
            rh->left = root;
        }
        else rt = root;
        
        return {lh, rt};
    }
};