题解 | #二叉搜索树与双向链表#

递归方法
W：
中序遍历，因为是二叉搜索树，需要定义全局变量防止递归值的改变，递归到最小值为头节点；
如果不是最小值，此时需要建立当前节点与上一个节点的连接；
N：
处理时需要判断上一个节点是否为空

class Solution {
public:
    //返回的第一个指针，即为最小值，先定为NULL
    TreeNode* head = nullptr;
    //中序遍历当前值的上一位，初值为最小值，先定为NULL
    TreeNode* pre = nullptr;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree== nullptr){
            return nullptr;
        }
        //中序遍历
        Convert(pRootOfTree->left);
        if(pre== nullptr){//递归到最小值,判断上一位是否为空
            head=pRootOfTree;
            pre=head;
        }
        else{ //note use else
            pRootOfTree->left=pre;
            pre->right=pRootOfTree;
            pre=pRootOfTree;
        }

        Convert(pRootOfTree->right);
        return head;
    }
};

迭代方法
W：中序迭代遍历，需要一个标志位来判断是否指向最左侧，赋值为头节点，其他类似于递归调用
修改指向。
N：进入循环判断 cur!=nullptr;
指针定义赋值为空；
每次处理一个节点if ...else...

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        stack<TreeNode*> st;
        if(!pRootOfTree) return nullptr;
          TreeNode* cur=pRootOfTree;
        TreeNode* pre=nullptr;//note 指针初始赋值为空
       TreeNode* head=nullptr;
        bool isFirst=false;
        while(cur!=nullptr || !st.empty()){
            if(cur!=nullptr){
               st.push(cur);
                cur=cur->left;
            }
            else{
                cur=st.top();
                st.pop();
                if(!isFirst){//find the top left node 
                    isFirst=true;
                    head=cur;
                    pre=head;
                }
                else{
                     pre->right=cur;
                     cur->left=pre;//note 互相指向
                     pre=cur;//更新pre;
                }
                cur=cur->right;//放在外面
            }
        }
        return head;
    }
};