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

非常规的递归思路，不用全局变量，时间复杂度很高

TreeNode* Convert(TreeNode* pRootOfTree) {
    if (!pRootOfTree)
        return nullptr;
    TreeNode* left = dfs(pRootOfTree->left, true);
    pRootOfTree->left = left;
    if (left)
        left->right = pRootOfTree;
    TreeNode* right = dfs(pRootOfTree->right, false);
    pRootOfTree->right = right;
    if (right)
        right->left = pRootOfTree;
    TreeNode* ret = pRootOfTree;
    while (ret->left)
        ret = ret->left;
    return ret;
}

TreeNode* dfs(TreeNode* root, bool isleft) {
    if (!root)
        return nullptr;

    TreeNode* left = dfs(root->left, true);
    root->left = left;
    if (left)
        left->right = root;
    TreeNode* right = dfs(root->right, false);
    root->right = right;
    if (right)
        right->left = root;

    if (isleft) {
        TreeNode* ret = root;
        while (ret->right)
            ret = ret->right;
        return ret;
    }
    else {
        TreeNode* ret = root;
        while (ret->left)
            ret = ret->left;
        return ret;
    }
}