C++二叉搜索树与双向链表(剑指Offer精简版)
题目:输入一棵二叉搜索树,将该二叉搜素树转换成一个排序的双向链表。
二叉树节点定义如下:
卓尼网站制作公司哪家好,找创新互联!从网页设计、网站建设、微信开发、APP开发、响应式网站设计等网站项目制作,到程序开发,运营维护。创新互联2013年开创至今到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联。
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);
}
};
当前标题:C++二叉搜索树与双向链表(剑指Offer精简版)
标题来源:http://myzitong.com/article/pddsog.html