具体的题目大意和参考思路在此处不详述(见《剑指offer》),实质就是在中序遍历的过程中调整指针的指向,关于中序遍历有递归和非递归两种操作,所以此处也用了两种方法。
方法1(递归法):
代码如下:
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == nullptr)
return nullptr;
TreeNode * pre = nullptr;//中序遍历中当前节点的前一个节点
ConvertCore(pRootOfTree,pre);
TreeNode * rs = pRootOfTree;
while(rs->left != nullptr)//经过转换后的pRootOfTree已经指到双向链表的末端
rs = rs->left;
return rs; }
void ConvertCore(TreeNode *cur ,TreeNode * &pre)
{
if(cur == nullptr)
return;
ConvertCore(cur->left,pre);
cur->left = pre;
if(pre != nullptr)
pre->right = cur;
pre = cur;
ConvertCore(cur->right,pre); }
};
关于递归法此处有几点需要注意:
1.实际整个过程中需要记录的节点只有一个:即在遍历过程中当前节点的前一个节点。在ConvertCore方法中,if(pre != nullptr)这一步是必须要加的,实际上是用来判断初始化时的情况。(pre初始化时为nullptr)
2.节点的left指针指向前一个节点,right指针指向后一个节点;最后返回的是rs这个指针(必须是链表的头指针)。
3.ConvertCore中的第二个参数为指针的引用,当然此处也可以是指向指针的指针即二级指针。因为函数中要操作的是指针变量本身,而不是指针变量指向的值。本题按情况类似于http://www.cnblogs.com/wangkundentisy/p/8586248.html
方法2(非递归):
代码如下:
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == nullptr)
return nullptr;
TreeNode * pre = nullptr;//中序遍历中当前节点的前一个节点
ConvertCore(pRootOfTree,pre);
TreeNode * rs = pRootOfTree;
while(rs->left != nullptr)//经过转换后的pRootOfTree已经指到双向链表的末端
rs = rs->left;
return rs; }
void ConvertCore(TreeNode *cur ,TreeNode * &pre)
{
if(cur == nullptr)
return;
stack<TreeNode*>s;
TreeNode *p = cur;
while(p || !s.empty())
{
if(p)
{
s.push(p);
p = p->left; }
else
{
p = s.top();
s.pop();
p->left = pre;
if(pre != nullptr)
pre->right = p;
pre = p;
p = p->right;
}
} }
};
关于非递归,感觉直接套模板,然后改改细节就能实现了,还是需要注意的一点就是if(pre != nullptr)这个判断不要忘记加。
总之,这种涉及指针的递归类问题很容易出错,一定要搞清楚整个逻辑过程,写完代码后,在心中照着代码执行一遍看看有没有出错。