描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
如下图所示
数据范围: 输入二叉树的节点数 0 ≤ n ≤ 1000,二叉树中每个节点的值 0 ≤ val ≤ 1000
要求: 空间复杂度 O(1)(即在原树上 *** 作),时间复杂度 O(n)
注意:
- 要求不能创建任何新的结点,只能调整树中结点指针的指向。
当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
- 返回链表中的第一个节点的指针
- 函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构
- 你不用输出双向链表,程序会根据你的返回值自动打印输出
输入描述: 二叉树的根节点
返回值描述: 双向链表的其中一个头节点。
示例1
输入: {10,6,14,4,8,12,16}
返回值: From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明:输入题面图中二叉树,输出的时候将双向链表的头节点返回即可。
示例2
输入: {5,4,#,3,#,2,#,1}
返回值: From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明:
5
/
4
/
3
/
2
/
1
树的形状如上图
已知将二叉搜索树进行中序遍历可以得到由小到大的顺序排列,因此本题最直接的想法就是进行中序遍历。
将中序遍历的结果用数组存储下来,得到的数组是有从小到大顺序的。
最后将数组中的结点依次连接即可。
示意图如下:
代码
class Solution {
public:
vector<TreeNode*> TreeList;//定义一个数组,根据中序遍历来存储结点。
void inorder(TreeNode* root){
if (!root) return;
inorder(root->left);
TreeList.push_back(root);
inorder(root->right);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
if (!pRootOfTree) return pRootOfTree;
inorder(pRootOfTree);
for (int i=0;i<TreeList.size()-1;i++){ //根据数组中的顺序将结点连接,注意i的范围。
TreeList[i]->right = TreeList[i+1];
TreeList[i+1]->left = TreeList[i];
}
return TreeList[0];//数组的头部存储的是双向链表的第一个结点。
}
};
运行时间:5ms
超过2.55% 用C++提交的代码
占用内存:520KB
超过25.03%用C++提交的代码
方法二
依旧采取中序遍历。
根据题目的要求1,不能创建新的结点,而方法一的数组中存储的其实是结点,并不满足题意;所以需要在中序遍历的过程中,直接对结点的指针进行调整。
调整的思路如下:
(1)使用一个指针preNode指向当前结点root的前继。
(例如root为指向10的时候,preNode指向8,如图所示:)
(2)对于当前结点root,有root->left要指向前继preNode(中序遍历时,对于当前结点root,其左孩子已经遍历完成了,此时root->left可以被修改。
);同时,preNode->right要指向当前结点(当前结点是preNode的后继),此时对于preNode结点,它已经完全加入双向链表。
代码
class Solution {
public:
vector<TreeNode*> TreeList;//定义一个数组,根据中序遍历来存储结点。
void inorder(TreeNode* root){
if (!root) return;
inorder(root->left);
TreeList.push_back(root);
inorder(root->right);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
if (!pRootOfTree) return pRootOfTree;
inorder(pRootOfTree);
for (int i=0;i<TreeList.size()-1;i++){ //根据数组中的顺序将结点连接,注意i的范围。
TreeList[i]->right = TreeList[i+1];
TreeList[i+1]->left = TreeList[i];
}
return TreeList[0];//数组的头部存储的是双向链表的第一个结点。
}
};
运行时间:3ms
超过33.82% 用C++提交的代码
占用内存:548KB
超过20.46%用C++提交的代码
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)