您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
题目:输入一棵二叉搜索树,将该二叉搜素树转换成一个排序的双向链表。
二叉树节点定义如下:
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
解题思路:
由于通过中序排序可以转化为双向链表,因此,通过中序遍历的方法(左根右)的递归方法可以解决问题,解决完之后,pList节点指向双向链表的尾结点,pList节点需要通过遍历,返回到头节点,同样,我们也可以通过逆向中序遍历的方法之间完成,代码如下:
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* pList=nullptr;//双向链表的头节点
Convert(pRootOfTree,pList);
return pList;
}
void Convert(TreeNode* pRootOfTree,TreeNode*& pList)
{
if(pRootOfTree==nullptr)//递归的出口
return;
if(pRootOfTree->right!=nullptr)//递归处理右子树
Convert(pRootOfTree->right,pList);
pRootOfTree->right=pList;//right相当于pNext
if (pList != nullptr)
pList->left = pRootOfTree;//left相当于pPre
pList = pRootOfTree;//pList节点从尾结点依次移动到头节点
if (pRootOfTree->left != nullptr)//递归处理左子树
Convert(pRootOfTree->left, pList);
}
};
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。