题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
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;
}
}; 时间复杂度：%2Cn%E6%98%AF%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0%EF%BC%8C%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E9%83%BD%E8%A2%AB%E8%AE%BF%E9%97%AE)
空间复杂度：%EF%BC%9B%5C%20%E7%90%86%E6%83%B3%E6%83%85%E5%86%B5%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E5%B9%B3%E8%A1%A1%EF%BC%8C%E9%80%92%E5%BD%92%E8%B0%83%E7%94%A8%E6%A0%88%E7%9A%84%E6%B7%B1%E5%BA%A6%E6%98%AFO(logn))
方法二：
直接模拟+空间优化
思路：利用中序遍历和一个指针实现。
指针 p 是（中序遍历序列中）当前节点 root 的上一个节点，通过这两个节点的连接，即可实现树的原地修改。
最后 指针p 会指向中序遍历序列的最后一个节点。然后通过 指针p 的循环前移操作 ，便可得到双向链表的首节点。
class Solution {
public:
TreeNode* p=nullptr;//中序遍历序列中的上一个节点
TreeNode* Convert(TreeNode* pRootOfTree) {
if(pRootOfTree==nullptr)
return nullptr;
f(pRootOfTree);
while(p->left){//链表指针从后往前遍历，找到第一个节点
p=p->left;
}
return p;
}
void f(TreeNode* root){
if(root==nullptr)
return;
f(root->left);//递归左儿子
root->left=p;
if(p)//如果p非空，则指针p的右指针 指向root
p->right=root;
p=root;
f(root->right);//递归右儿子
}
}; 时间复杂度：
空间复杂度：%EF%BC%9B%0A%5C%20%E7%90%86%E6%83%B3%E6%83%85%E5%86%B5%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E5%B9%B3%E8%A1%A1%EF%BC%8C%E9%80%92%E5%BD%92%E8%B0%83%E7%94%A8%E6%A0%88%E7%9A%84%E6%B7%B1%E5%BA%A6%E6%98%AFO(logn))
科大讯飞公司氛围 440人发布
查看10道真题和解析