《剑指offer》-二叉搜索树与双向链表
2024-10-17 21:27:20
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
题目的描述不是很习惯。题目的意思是把二叉树从左到右遍历，相当于双向链表的遍历。
其实就是让二叉树在x方向上的投影点，顺序输出。那么其实就是中序遍历。递归版本如下：
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* root){
if (root == NULL) return root;
root = ConvertNode(root);
while (root->left){
root = root->left;
}
return root;
}
TreeNode* ConvertNode(TreeNode* root){
if (root == NULL) return root;
if (root->left){
TreeNode* left = ConvertNode(root->left); //重要。是递归而不是仅仅取一个节点。
while (left->right){
left = left->right;
}
left->right = root;
root->left = left;
}
if (root->right){
TreeNode* right = ConvertNode(root->right); //重要。是递归而不是仅仅取一个节点。
while (right->left){
right = right->left;
}
right->left = root;
root->right = right;
}
return root;
}
};
最新文章
- iOS推送处理
- 【caffe】无法找到gpu/mxGPUArray.h: No such file or directory
- linux文档常见后缀名
- Buffer和Cache的区别
- css知识点积累
- java动态生成带下拉框的Excel导入模板
- Android 内核初识(4)属性服务器
- RMAN综合学习之备份
- Linux下crontab命令详解
- ext中嵌入flash
- 常用CSS代码片断
- 转载：JSONObject.fromObject(map)（JSON与JAVA数据的转换）
- HUSTOJ：Transit Tree Path
- Loadrunner常用目录、组成部分及负载测试流程
- Node 开启
- C#打印标签
- 不用ajax实现异步请求：XmlHttpRequest 小记
- day 11 生成器
- .Net Standard 类库的创建和使用
- UrlRewriter && IIS7