剑指offer#36.二叉搜索树和双向链表

二叉搜索树和双向链表：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：因为是二叉搜索树，所以有左小右大，中序遍历有序的特性。因此要利用其中序遍历有序的特性，来进行转换。
那么如果采用中序遍历，遍历到某个节点，要处理它的时候，就说明它的左子树已经处理好了，那么就可以修改它的左孩子指针，但是其右子树还没有遍历，所以还不可以修改它的右孩子指针，那么怎么办呢？因为中序遍历下一个结点一定是其前一个节点的后驱节点，因此需要用一个pre指针来指向其前驱节点，当遍历到下一个节点的时候，判断pre不为空我们就可以修改pre的右孩子指针指向本节点。
但是这时候又要考虑一个问题，假如我们使用的是中序的递归算法，我们的pre如果不用&的话呢，无法保存后面修改返回来的pre，所以要用&符号。还有一个问题是pre是必须到最左节点才能修改，所以在向左递归的过程中，pre始终不变，等到向右遍历的时候才开始变化！
解法一：使用非递归中序遍历，只需要保存好一个pre即可，这个pre就一定会在最左处修改，之后开始不断更新，然后退出的时候，p为null，pre为链尾节点，所以要向前遍历找到链头

TreeNode* Convert(TreeNode* pRootOfTree)
    {
        //如果我用非递归中序遍历
        if(pRootOfTree == nullptr)
            return nullptr;
        stack<TreeNode*> s;
        TreeNode* pre = nullptr;
        while(pRootOfTree || !s.empty()){
            if(pRootOfTree){
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree->left;
            }else{
                TreeNode* cur = s.top();
                s.pop();
                cur->left = pre;
                if(pre != nullptr){
                    pre->right = cur;
                }
                pre = cur;
                pRootOfTree = cur->right;
            }
        }
        while(pre->left){
            pre = pre->left;
        }
        return pre;
    }

解法二：使用递归算法，其实就是把解法一改成递归的形式，那么特别注意的是pre要等到最左才能改变，所以在向左遍历的时候，pre始终传递原来的pre，等到向右传递的时候再把pre不断更新。
还有一个问题是pre一定要用&,不然无法保存住上一次修改的pre。

比如说要是走到了5，这时候pre还是null
接着走到3，3的pre也是null
然后3会往左右走，直接返回后就处理3自己，一处理完就修改，把pre修改成了3，然后返回到5
如果不用引用的话，此时返回到5会恢复其pre的内容，也就是null，所以要用&,采用使pre变成3！！！！！
如果不想用来传递，也可以把pre设置成全局变量，这样就类似非递归遍历了

TreeNode* Convert1(TreeNode* pRootOfTree)
    {
        //先连成一个单链表试一下
        //要用中序遍历
        if(pRootOfTree == nullptr)
            return nullptr;
        TreeNode* pre = nullptr;
        ConvertCore(pRootOfTree,pre);
        //最后返回的是链尾节点,然后要逆序遍历到头节点
        TreeNode* head = pRootOfTree;
        while(head->left){
            head = head->left;
        }
        return head;
    }
    //此处的pre一定得传引用，因为我们当前处理节点的pre是必须受上一次处理
    //pre的改变的影响的，如果不受影响则
    void ConvertCore(TreeNode* pRootOfTree,TreeNode*& pre){
        //中序遍历
        if(pRootOfTree){
            ConvertCore(pRootOfTree->left,pre);
            pRootOfTree->left = pre;
            if(pre != nullptr)
                pre->right = pRootOfTree;
            pre = pRootOfTree;
            ConvertCore(pRootOfTree->right,pre);
        }
    }