二叉搜索树与双向链表 中序遍历的递归和栈解法

//参考 c++二叉树：层序，前，中，后 序遍历的解题模板：https://blog.csdn.net/sinat_36338365/article/details/107916628 /*

class Solution {
public:
    TreeNode* head=NULL,*L=NULL;
    TreeNode* Convert(TreeNode* pRootOfTree)
    {//中序遍历：左，根，右
 //方法一：使用递归的中序遍历
        if (!pRootOfTree)return pRootOfTree;
        if(pRootOfTree->left)Convert(pRootOfTree->left);
        if(head==NULL){                  //其他都是中序遍历的模板，
            head=pRootOfTree;           //只有这一块是本道题需要额外附加的
            L=head;                     //
        }                               //
        else{                          //
            L->right=pRootOfTree;     //
            pRootOfTree->left=L;      //
            L=pRootOfTree;           //
        }                            ////二叉树的前中后序遍历模板参考https://blog.csdn.net/sinat_36338365/article/details/107916628         if(pRootOfTree->right)Convert(pRootOfTree->right);
        return head;
//方法二：非递归，采用stack堆栈的形式的中序遍历
        /*TreeNode* p = pRootOfTree;
        stack<TreeNode*> st;
        TreeNode* head=NULL,*L=NULL;
        while (p||!st.empty()) {
            while (p) {
                st.push(p);
                p= p->left;
            }
            if(!st.empty()) {
                p = st.top();
                st.pop();                
                //cout << p->val << " ";//其他都是中序遍历的模板，
                    if(head==NULL){     //
                        head=p;        //只有这一块是本道题需要额外附加的
                        L=p;          //
                    }                 //
                    else {            //
                        L->right=p;  //
                        p->left=L;   //
                        L=p;         //
                        }            //
                                     // 二叉树的前中后序遍历模板参考：https://blog.csdn.net/sinat_36338365/article/details/107916628
​                        p = p->right;
            }
        }
        return head;*/
    }
};