时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
本题解法将分两步来完成
- 中序遍历（LDR）对二叉搜索树进行遍历，并将整个节点存储到TreeNode*类型的vector容器中
- 遍历vector容器利用节点的left、right指针进行双向链表的连接
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == NULL) return NULL; vector<TreeNode*> treeElem; LRD(pRootOfTree,treeElem); return Tree2Link(treeElem); } void LRD(TreeNode *root,vector<TreeNode*> &saveElem) { if(root == NULL) return ; LRD(root->left,saveElem); saveElem.push_back(root); LRD(root->right,saveElem); } TreeNode *Tree2Link(vector<TreeNode*> &treeElem) { for(int i = 0;i < treeElem.size()-1;i++) { treeElem[i]->right = treeElem[i+1]; } treeElem[treeElem.size()-1]->right = NULL; for(int i = treeElem.size()-1;i>=0;i--) { treeElem[i]->left = treeElem[i-1]; } treeElem[0]->left = NULL; return treeElem[0]; } };
当然，还存在更好的实现方法，如：Morris遍历等，可具体参考牛客网本题的讨论https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
原文链接: https://www.cnblogs.com/whiteBear/p/12565272.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/337753
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
