题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
题意：
方法：
中序遍历
思路：二叉搜索树的中序遍历是有序的。因此，我们对二叉搜索树中序遍历，并将结果存入一个双向链表中。
class Solution {
public:
TreeNode *head,*p;//新建双向链表
int i=0;
TreeNode* Convert(TreeNode* pRootOfTree) {
if(pRootOfTree==nullptr){
i++;
return nullptr;
}
Convert(pRootOfTree->left);//递归左儿子
if(i==1){//当遍历到最左下角时，则是链表的第一个节点
head=pRootOfTree;
p=pRootOfTree;
}else{//否则，拼接链表的其他节点
p->right=pRootOfTree;
pRootOfTree->left=p;
p=p->right;
}
Convert(pRootOfTree->right);//递归右儿子
return head;
}
};
时间复杂度：%2C%E9%81%8D%E5%8E%86%E9%93%BE%E8%A1%A8%E3%80%82)
空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
