依照题意，我们来撸一撸二叉树是如何形成链表的：

      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.

教训是：不要生搬硬套经典算法，应该沉下心理顺问题的思路，如这道题就是动手画一画变化过程。就非常容易发现其中的关窍了。