将二叉搜索树转化为排序的双链表。又是一道两种DS之间的转化，这两种指针都很多，一定要注意别丢。

看到BST，我就想到中序遍历就是排序，然后是否可以边遍历边调整指针，最后结束就是DLL呢？
关键是不能丢指针，plast p可以保持遍历过程的前后关系，这种思路在程设里屡见不鲜，例如fibonacci数列的遍历，用backtwo backone current记录当前和前两个的关系，只要前k这个k是常数，就可以
通过用k个变量来记录这种关系，空间复杂度仍然O(1), 前后关系要么是坐下走的时候，因为left已经被使用了，所以plast不丢left指针，p是否丢right指针？也不丢，因为从left跳到right是通过pop栈来找到parent的，
所以修改p的right指针是不影响的，后面各种情况下中序的前后关系修改left right指针都不影响后面的中序遍历的，所以完全可以通过中序遍历来实现这一过程。

TreeNode* BST->DoubleLinklist(TreeNode* root)//based on PreOrder and InOrder Traverse
{
    if(root==NULL) return NULL;
    TreeNode* p=root, *head, *plast;
    bool first=true;

    while(!S.empty() || p!=NULL)
    {
        while(p!=NULL)
        {
            S.push(p);
            p=p->left;
        }
        p=S.top();
        S.pop();

        if(first==true)
        {
            head=p;
            first=false;
            head->left=NULL;
        }
        else
        {
            plast>right=p;
            p->left=plast;
        }
        plast=p;

        p=p->right;
    }
    plast->right=NULL;
}

后来看了答案，发现其实不需要初始化head 和tail两个指针的left 和right因为 初始时一定都是NULL，head必为最左下，tail必为最右下

Posted by richard爱闹 - 7月 28 2014
如需转载，请注明： 本文来自 Richard