一、题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向
二、输入描述
输入一棵二叉搜索树
三、输出描述
将该二叉搜索树转换成一个排序的双向链表
四、牛客网提供的框架
/*
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)
{
}
};五、解题思路
按照中序遍历，按照左子树、根节点、右子树的顺序。
六、代码
#include<iostream>
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* newHead;
TreeNode* currNode;
TreeNode* Convert(TreeNode* pRootOfTree)
{
newHead = NULL;
currNode = NULL;
midOrder(pRootOfTree);
return newHead;
}
void midOrder(TreeNode* pRootOfTree) //中序（递归）遍历
{
if(!pRootOfTree) return;
if(pRootOfTree->left) midOrder(pRootOfTree->left); //左子树
//加入链表
if(!newHead) //是否是第一个节点
{
newHead = pRootOfTree;
currNode = pRootOfTree;
}
else
{
currNode->right = pRootOfTree;
pRootOfTree->left = currNode;
currNode = pRootOfTree;
}
if(pRootOfTree->right) midOrder(pRootOfTree->right); //右子树
}
};