Convert a Binary Search Tree to Double linked list | Cracking Programming

[微软面试100题系列01]输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
此题本质上是考察中序遍历，只是稍微延伸了一下，顺便考了双链表的概念和创建步骤

void convertBSTToDLL(treenode* curNode, treenode*& prevNode, treenode*& listHead)
{
    if (curNode)
    {
        convertBSTToDLL(curNode->left, prevNode, listHead);
        if (prevNode)
        {
            curNode->left = prevNode;
            prevNode->right = curNode;
        }
        else
        {
            listHead = curNode;
        }
        prevNode = curNode;
        convertBSTToDLL(curNode->right, prevNode, listHead);
    }
    return;
}

Iterative Version:

    public static BSTreeNode resort(BSTreeNode root) {

        Stack<BSTreeNode> stack = new Stack<BSTreeNode>();

        BSTreeNode head = null;

        BSTreeNode cur = null;

        while (root != null || !stack.isEmpty()) {

            while (root != null) {

                stack.push(root);

                root = root.left;

            }

            if (!stack.isEmpty()) {

                root = stack.pop();

                if(cur == null){

                    head = root;

                    head.left = null;

                    cur = root;

                }else{

                    cur.right = root;

                    root.left = cur;

                    cur = cur.right;

                }

                root = root.right;

            }

        }

        return head;

    }

Also check http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.html
Read full article from Convert a Binary Search Tree to Double linked list | Cracking Programming