手撸一版
class Solution {
public:
TreeNode* pre=nullptr; // 用来保存尾节点
TreeNode* convert(TreeNode* root) { // 返回头结点
if(!root){
pre=root;
return nullptr;
}
auto l=convert(root->left);
root->left=pre;
if(pre) pre->right=root;
pre=root;
auto r=convert(root->right);
root->right=r;
if(r) r->left=root;
if(!pre) pre=root;
if(!l) return root;
return l;
}
/*
整体思路非常简单:
递归法
1.和左链的尾节点建立联系(因此需要pre指针保存尾节点) 2.和右链的头结点建立联系
需要注意:如果没有左链则返回自己、如果没有右链则pre设为自己
*/
};