114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

---

把一棵二叉树展开成一个链表，链表还是借助树的数据结构，只不过是借用了树的右孩子指针作为链表的指针。 仔细观察发现新的链表的顺序和树的先序遍历的顺序一致，如果能使用额外的空间，则先序遍历后把节点存到数组中，然后依次链接起来。 如果不使用额外空间，则只能想办法在DFS时就建立好链接关系。先序遍历的顺序是根左右，但是这题为了方便，我们先对右孩子建立链表，然后把右孩子接到父亲的左孩子的最右下角的节点上。比如上图中，我们建立好5->6的链表之后，需要把它接到4号节点的右边。

         1
        /
       2
      / \
     3   4
          \
           5
            \
             6

所以针对右孩子，我们需要根据父节点找到父节点的左子树的最右下角的节点。但是针对左孩子时，因为此时右孩子已经建立好链表并且接到了左孩子正确的位置上，所以只需要把左孩子接到父亲的右孩子位置，并把原来的左孩子置空，下图就是把上图1的左子树放到了右边，左边置为空。

   1
     \
       2
      / \
     3   4
          \
           5
            \
             6

完整代码如下：

class Solution2 {
public:
    void dfs(TreeNode* par, TreeNode* cur)
    {
        if (cur == NULL)
            return;
        if (par) {
            if (cur == par->right) {
                if (par->left) {
                    TreeNode* tmp = par->left;
                    while (tmp->right)
                        tmp = tmp->right;
                    tmp->right = cur;
                    par->right = NULL;
                }
            }
            else {
                par->right = cur;
                par->left = NULL;
            }
        }
        if (cur->right)
            dfs(cur, cur->right);
        if (cur->left)
            dfs(cur, cur->left);
    }
    void flatten(TreeNode* root) { dfs(NULL, root); }
};

本代码提交AC，用时6MS。
还有一种思路比这简单，上面的解法需要while循环查找左兄弟的最右下角的节点，如果我们在DFS中直接返回尾节点，就不需要while查找了。
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：
1
/    \
2     5
\       \
3      6 <- rightTail
\
4  <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：
leftTail->right = root->right;
root->right = root->left;
root->left = NULL;
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
代码如下：

class Solution {
public:
    TreeNode* dfs(TreeNode* root)
    {
        if (!root)
            return NULL;
        TreeNode* leftTail = dfs(root->left);
        TreeNode* rightTail = dfs(root->right);
        if (root->left) {
            leftTail->right = root->right;
            root->right = root->left;
            root->left = NULL;
        }
        if (rightTail)
            return rightTail;
        if (leftTail)
            return leftTail;
        return root;
    }
    void flatten(TreeNode* root) { dfs(root); }
};

本代码提交AC，用时6MS。