【递归，链表，BST】将BST转换成双向链表

• 既然是一棵树，可以考虑递归做法。

  • 如果左子树和右子树都已经处理好了，该怎么组合成一个新的链表？
  • 有点类似数学归纳法的思路

• 以图片为例，左子树和右子树处理好之后，返回红色节点为head的双向链表，所以只需要将这两段链表和root合并即可

  • 合并之后返回的仍然是左子树的head（若有）

• 边界情况

  • 若整个树为空，显然应该返回nullptr
  • 若左子树为空，则答案的head应该为root
  • 若右子树为空，则root->right 自然是nullptr，不需要特别处理

code：

TreeNode* Convert(TreeNode* pRootOfTree){
        //处理空树
        if(pRootOfTree == nullptr)
            return nullptr;
        TreeNode * ans = nullptr;
        //处理左子树（若有）
        if(pRootOfTree->left){
            ans = Convert(pRootOfTree->left);
            auto tail = ans;
            while(tail->right)
                tail = tail->right;
            tail->right = pRootOfTree; //处理左子树链表和root的衔接
            pRootOfTree->left = tail;
        }else ans = pRootOfTree; //若无左子树，head设置为root
        if(pRootOfTree->right){ //处理右子树
            auto nxtHalf = Convert(pRootOfTree->right);
            nxtHalf->left = pRootOfTree;
            pRootOfTree->right = nxtHalf;
        }
        return ans;
    }