114. 二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode）

class Solution {
  TreeNode *Prev;
  TreeNode *Head;

  void traverse(TreeNode *TN, int Depth) {
    if (!TN)
      return;

    if (Prev) {
      Prev->right = new TreeNode(TN->val);
      Prev = Prev->right;
    } else {
      Head = Prev = new TreeNode(TN->val);
    }

    traverse(TN->left, Depth + 1);
    traverse(TN->right, Depth + 1);

    if (Depth > 0)
      delete TN;
  }

public:
  void flatten(TreeNode* root) {
    if (!root)
      return;
    traverse(root, 0);

    *root = *Head;
    delete Head;
  }
};

我这个解法完全是 hack 来的，有点崩溃。

这道二刷的时候要用前序、反前序和前驱思路再写一遍。

二刷

class Solution {
public:
  void flatten(TreeNode* root) {
    if (!root)
      return;

    // Process left tree.
    flatten(root->left);

    // When finished, move left tree onto right branch.
    TreeNode *Right = root->right;
    root->right = root->left;
    // And connect to original branch.
    TreeNode *Temp = root;
    TreeNode Dummy(0, nullptr, root), *Prev = &Dummy;
    while (Temp) {
      Temp = Temp->right;
      Prev = Prev->right;
    }
    Prev->right = Right;
    root->left = nullptr;

    // Continue processing right tree.
    flatten(root->right);
  }
};

其实这个递归方法非常容易想到，就是每次退栈的时候把左子树嫁接到右子树上。也很容易用非递归方法改写。但是 $\mathrm O(1)$ 的思路我确实没见过。

class Solution {
public:
  void flatten(TreeNode* root) {
    TreeNode *Curr = root;
    while (Curr) {
      TreeNode *Left = Curr->left;
      if (Left) {
        TreeNode *Pred = Left;
        while (Pred->right)
          Pred = Pred->right;
        // Move successors onto left rightmost branch.
        Pred->right = Curr->right;
        // Move the whole left branch onto right.
        Curr->left = nullptr;
        Curr->right = Left;
      }
      // Already moved onto right. We can safely progress now.
      Curr = Curr->right;
    }
  }
};

这个思路是根据莫里斯遍历改写的，它是一种可以实现 $\mathrm O(1)$ 空间的遍历方法——其实就是利用叶子结点的空余指针构造线索二叉树。它在算法当中是有一席之地的。

这种解法更狠，压根就不需要等什么退栈不退栈的，人家直接利用前序遍历「左子树的最右节点是右子树的前驱」的性质，在莫里斯遍历的基础上，不是创建线索，而是把右子树直接拉下来。记代码属实是不太好记，但是力扣官方题解里给的动图倒是挺直观的，可以用这个记一下。

还有一种仍然采用递归的 $\mathrm O(n)$ 空间遍历是反前序遍历，如果在这种遍历的途中输出结果的话，最后的结果就和前序遍历完全相反。假设前序遍历顺序是

$$ 1\ 2\ 3\ 4\ 5\ 6 $$

那么它的遍历顺序自然也就是

$$ 6\ 5\ 4\ 3\ 2\ 1 $$

这种遍历采用回溯的思路——第一次遍历到的节点是前序遍历中最后的节点 $6$，那么它就是所有节点的后缀节点，我们可以把它记录在 Suffix 变量当中；第二次遍历到的是 $5$，那么我们很自然地就可以形成 $5\to6$ 这种链条，并且把 Suffix 赋值为 $5$……以此类推，最终得到 $1\to2\to3\to4\to5\to6$ 的完整链条，并返回 Suffix。

class Solution {
  TreeNode *Suffix{};
public:
  void flatten(TreeNode* root) {
    if (!root)
      return;
    flatten(root->right);
    flatten(root->left);
    root->left = nullptr;
    root->right = Suffix;
    Suffix = root;
  }
};

反前序遍历最大的特点在于，它事实上是一种后序遍历，而后序遍历的计算能力其实是 $\mathrm{LR}(0)$ 级别的！所以我们很自然地就获取了比单纯的前序遍历多得多的信息，也就不至于像我写的前序一样这么麻烦。

这个确实太优雅了，我靠。两种都好优雅，一种是空间 $\mathrm O(1)$ 的优雅，一种是递归可计算性的优雅。

三刷

class Solution {
public:
  void flatten(TreeNode* root) {
    TreeNode *This = root;
    while (This) {
      TreeNode *Left = This->left;
      if (Left) {
        while (Left->right)
          Left = Left->right;
        Left->right = This->right;
        // The following two statements are critical. Especially the assign-to-
        // nullptr one. This prevents multiple reference.
        This->right = This->left;
        This->left = nullptr;
      }
      This = This->right;
    }
  }
};

其实没什么好说的，图示能画明白就可以了。但是注意 This->left = nullptr; 这一句不能漏，否则会产生重复引用而导致资源释放出现问题。

四刷

class Solution {
public:
  void flatten(TreeNode* root) {
    if (!root)
      return;

    TreeNode *Batch = root;
    // Only one layer of loop is enough.
    while (Batch) {
      if (Batch->left) {
        TreeNode *Cont = Batch->right;
        Batch->right = Batch->left;
        Batch->left = nullptr;
        TreeNode *Dispatch = Batch->right;
        // Connect the thread that's been cut.
        while (Dispatch->right)
          Dispatch = Dispatch->right;
        Dispatch->right = Cont;
      }
      Batch = Batch->right;
    }
  }
};

其实这种解法的关键就在于while (Batch)只需要一层而不需要更多层，结果就是得到了$\mathrm O(n)$的时间和$\mathrm O(1)$的空间，这也是利用了树作为递归数据结构的特性。