只需要在非递归的中序遍历的时候, 在原先输出节点的时候, 将当前节点的left指向链表的队尾, 队尾的right指向当前节点, 然后当前节点变成新的队尾.
用head记录一下遍历到的第一个节点, 最后返回head即可.

class Solution {
public:
    TreeNode* convert(TreeNode* root) {
        stack<TreeNode *> stk;
        TreeNode *head = NULL, *pre = NULL;
        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();          // 前面的代码和中序遍历的一模一样

            if (!head) head = pre = root;
            else {
                pre->right = root;
                root->left = pre;
                pre = root;
            }

            root = root->right;
        }
        return head;
    }
};