剑指offer 面试题36.二叉搜索树与双向链表
2024-10-08 09:19:39
中序递归，一个pre节点记录前一个节点
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* pre=nullptr;
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==nullptr){
return nullptr;
}
func(pRootOfTree);
while(pRootOfTree->left){
pRootOfTree=pRootOfTree->left;
}
return pRootOfTree;
}
void func(TreeNode* pRootOfTree){
if(pRootOfTree==nullptr){
return;
}
Convert(pRootOfTree->left);
if(pre!=nullptr){
pre->right=pRootOfTree;
pRootOfTree->left=pre;
}
pre=pRootOfTree;
Convert(pRootOfTree->right);
}
};
中序迭代，一个pre节点记录前一个节点
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* pre=nullptr;
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==nullptr){return nullptr;}
stack<TreeNode*> sta;
TreeNode* cur=pRootOfTree;
while(cur or not sta.empty()){
if(cur){
sta.push(cur);
cur=cur->left;
}
else{
cur=sta.top();
sta.pop();
if(pre!=nullptr){
pre->right=cur;
cur->left=pre;
}
pre=cur;
cur=cur->right;
}
}
while(pRootOfTree->left){
pRootOfTree=pRootOfTree->left;
}
return pRootOfTree;
}
};
递归，func(root)将root为根的子树转化为双向链表，返回长度为2的vector，vec[0]为子树链表的头，vec[1]为尾。
/*
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)
{
return func(pRootOfTree)[0];
}
vector<TreeNode*> func(TreeNode* root){
if(root==nullptr){return {nullptr,nullptr};}
auto vec_le=func(root->left);
auto vec_ri=func(root->right);
if(vec_le[1]!=nullptr){
vec_le[1]->right=root;
root->left=vec_le[1];
}
if(vec_ri[0]!=nullptr){
vec_ri[0]->left=root;
root->right=vec_ri[0];
}
vector<TreeNode*> res(2,root);
if(vec_le[0]!=nullptr){
res[0]=vec_le[0];
}
if(vec_ri[1]!=nullptr){
res[1]=vec_ri[1];
}
return res;
}
};
最新文章
- Debian8.3安装flash插件，备用～～～
- 《CLR.via.C#第三版》第二部分第13章节 接口 读书笔记(七)
- September 8th 2016 Week 37th Thursday
- 用AutoHotKey彻底解决“Ctrl键+鼠标滚动”时的缩放问题
- ios app 实现热更新（无需发新版本实现app添加新功能）
- Facebook三种分享方式
- uva 307
- Android学习系列(1)--为App签名(为apk签名)
- logback使用笔记
- poj2392 Space Elevator(多重背包)
- 【floyed】【HDU1217】【Arbitrage】
- mybatis学习笔记三（关联关系）
- 常见的JQuery应用举例
- 2017-07-20聊聊《C#本质论》
- JavaScript基本概念
- ReSharper 自动选中
- Trap 冷启动与热启动告警
- JS创建对象的几种方式整理
- Redis入门到高可用（十五）—— HyperLogLog
- Qt Installer Framework 使用说明（三）