依照题意，我们来撸一撸二叉树是如何形成链表的：
1 1 1 1 1
/ \ / \ \ \
2 5 ===> 2---> ===> 2 ===> 2 ===> 2
/ \ |\ / \ / \ / \
3 4 | 6 3 4 3 4 3---> 3
^ | \ <_|\ \ \
|_| 5 5 4 4
\ \ \ \
6 6 5 5
\ \
6 6
(1) (2) (3) (4) (5)
####(1) -> (2)
TreeNode *end = root->left; // DFS 定位**左子树的最右节点**
while (end->right) end = end->right; // 如图，最终 end 指向 4.
end->right = root->right; // 将 end 指向右子树的头####(2) -> (3) 此刻 1 的右指针还指向着 5->6，应该要改为指向 2.
root->right = root->left; // 右指针指向左子树
root->left = NULL; // 左指针指空####(3) -> (4)
root = root->right; // 进行下一层次的迭代(3) -> (4) -> (5) 重复了上面 (1) -> (2) -> (3) 的过程，只不过 root 由 1 换为了 2.
这道题让我意识到我已经形成了思维惯性。
首先，树的题，先考虑递归算法，但这并非是很明显的尾递归，因为左子树和右子树的连接显然是需要左子树的最右节点。而并非根节点。
不考虑递归，因为是 DFS, 那么很显然就想到了堆栈，于是比较愚蠢的先深搜到最左节点，然后回溯，去连找到的右节点，再回溯，继续连右。
最后的确也 AC 了，然空间复杂度是 logN 的，显然没有上面的 O(1) nice.
教训是：不要生搬硬套经典算法，应该沉下心理顺问题的思路，如这道题就是动手画一画变化过程。就非常容易发现其中的关窍了。