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

二叉搜索树与双向链表

题目链接：二叉搜索树与双向链表

解题思路1：递归+中序遍历

首先题目最后要求的是一个的递增的双向链表，而二叉搜索树也是一类非常有特色的树，它的根节点大于所有左侧的节点，同时又小于所有右侧的节点，如果我们按照左中右去遍历这颗二叉树，恰巧得到的就是一个递增序列

题目同时要求不要创建新的节点，这样我们就需要在原有树上进行操作，树有左右节点指针，双向链表有前后两个指针，正好一一对应，我们修改指针指向，结合中序遍历，得到一颗递增的双向链表

代码如下：

	TreeNode* head = nullptr;TreeNode* pre = nullptr;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;//递归的结束条件Convert(pRootOfTree->left);//递归到最左节点，是最小值if(pre == nullptr){//此时pRootOfTree是最左节点，是链表的head//初始化head和prehead = pRootOfTree;pre = pRootOfTree;}else{//pre是每一个pRootOfTree的前驱节点pre->right = pRootOfTree;pRootOfTree->left = pre;pre = pRootOfTree;}Convert(pRootOfTree->right);return head;}

解题思路2：非递归+栈

我们利用栈先进后出的特性，来模拟中序遍历出所有元素，先让所有左侧的元素进栈，再依次取出其父节点，再找该节点的右节点，将节点进行连接，连接方式和上一种思路一样

    TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;TreeNode* head = nullptr;TreeNode* pre = nullptr;stack<TreeNode*> s;while(pRootOfTree!=nullptr || !s.empty()){while(pRootOfTree!=nullptr){s.push(pRootOfTree);pRootOfTree = pRootOfTree->left;}pRootOfTree = s.top();s.pop();if(pre == nullptr){head = pRootOfTree;pre = pRootOfTree;}else{pre->right = pRootOfTree;pRootOfTree->left = pre;pre = pRootOfTree;}pRootOfTree = pRootOfTree->right;}return head;}