题目:
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向
代码:
思路采用递归的方式实现(类似树的中序遍历),定义一个已经调整好的链表的左端节点指针和右端节点指针
#include "pch.h"
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution {
public:
TreeNode *L = NULL, *R = NULL;
TreeNode* Convert(TreeNode* pRootOfTree)
{
change(pRootOfTree);
return L;
}
void change(TreeNode* pRoot) {
if (pRoot->right == NULL && pRoot->left == NULL) {
if (L == NULL && R == NULL)
L = pRoot, R = pRoot;
else {
R->right = pRoot;
pRoot->left = R;
R = pRoot;
}
return;
}
else {
if (pRoot->left)change(pRoot->left);
if (L == NULL && R == NULL)L = pRoot, R = pRoot;
else {
R->right = pRoot;
pRoot->left = R;
R = pRoot;
}
if (pRoot->right)change(pRoot->right);
}
}
};
//用来进行测试的代码
//将输入的string转换为一种任意已知类型的函数
template <class T>
T string_to_double(const string& str)
{
istringstream iss(str);
T dou_num;
iss >> dou_num;
return dou_num;
}
void creat_tree(TreeNode* &R)
{
//int r;
string str;
cin >> str;
if (str == "#")
{
R = NULL;
}
else
{
int r = string_to_double<int>(str);
TreeNode *root = new TreeNode(r);
cout << "root(" << r << ")------>Leftchildren:" << endl;
creat_tree(root->left);
cout << "root(" << r << ")------>rightchildren:" << endl;
creat_tree(root->right);
R = root;
}
}
void main()
{
/*
TreeNode *r = new TreeNode(2);
r->left = new TreeNode(1);
r->right = new TreeNode(3);
*/
TreeNode *r;
cout << "请输入根节点:" << endl;
creat_tree(r);
Solution s;
s.Convert(r);
TreeNode *ss = s.L;
while (ss != s.R) {
cout << ss->val << " ";
ss = ss->right;
}
cout << s.R->val << endl;
ss = s.R;
while (ss != s.L) {
cout << ss->val << " ";
ss = ss->left;
}
cout << s.L->val << endl;
cout <<"result"<< endl;
}
结果:
注:在这个题上有一些问题,下面的代码在vs2017中能够通过,写了几个例子都没有问题,但是在牛客网上编译结果总是有段错误,没有找到原因