C++二叉搜索树与双向链表(剑指Offer精简版)-创新互联
题目:输入一棵二叉搜索树,将该二叉搜素树转换成一个排序的双向链表。
二叉树节点定义如下:
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);
}
};
另外有需要云服务器可以了解下创新互联cdcxhl.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
名称栏目:C++二叉搜索树与双向链表(剑指Offer精简版)-创新互联
文章网址:http://scyanting.com/article/icocd.html