114.Flatten Binary Tree to Linked List

分治

考虑分治，假如我们计算出了 root=1 左子树的链表 2→3→4，以及右子树的链表 5→6，那么接下来只需要穿针引线，把节点 1 和两条链表连起来：

先把 2→3→4 和 5→6 连起来，也就是左子树链表尾节点 4 的 right 更新为节点 5（即 root.right），得到 2→3→4→5→6。然后把 1 和 2→3→4→5→6 连起来，也就是节点 1 的 right 更新为节点 2（即 root.left），得到 1→2→3→4→5→6。最后把 root.left 置为空。上面的过程，我们需要知道左子树链表的尾节点 4。所以 DFS 需要返回链表的尾节点。

链表合并完成后，返回合并后的链表的尾节点，也就是右子树链表的尾节点。如果右子树是空的，则返回左子树链表的尾节点。如果左右子树都是空的，返回当前节点。

/**
 * 将二叉树原地展开为单链表（仅使用 right 指针）
 * 展开规则：按照二叉树的前序遍历顺序，将所有节点依次串联在 right 指针上，left 指针置为 null
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {TreeNode} - 展开后链表的最后一个节点（尾节点）
 */
var flatten = function (root) {
  // 递归终止条件：如果当前节点为 null，直接返回 null（空树没有尾节点）
  if (root === null) {
    return null
  }

  // 递归处理左子树，返回左子树展开后的尾节点
  // 递归会先把左子树完整展开为单链表，并返回该链表的最后一个节点
  const leftTail = flatten(root.left)

  // 递归处理右子树，返回右子树展开后的尾节点
  // 同理，递归会把右子树完整展开为单链表，并返回该链表的最后一个节点
  const rightTail = flatten(root.right)

  // 如果左子树存在（即 leftTail 不为 null），需要将左子树链表合并到当前节点和右子树之间
  if (leftTail) {
    // 步骤1：将左子树链表的尾节点的 right 指向原右子树链表的头节点（root.right）
    // 这样左子树链表就和右子树链表连接起来了
    leftTail.right = root.right

    // 步骤2：将当前节点的 right 指向原左子树链表的头节点（root.left）
    // 这样当前节点就和左子树链表连接起来，完成整体串联
    root.right = root.left

    // 步骤3：将当前节点的 left 置为 null，符合单链表的要求
    root.left = null
  }

  // 返回当前子树展开后的尾节点，优先级：
  // 1. 右子树的尾节点（rightTail）：如果右子树存在，尾节点一定是右子树的尾节点
  // 2. 左子树的尾节点（leftTail）：如果右子树不存在但左子树存在，尾节点是左子树的尾节点
  // 3. 当前节点（root）：如果左右子树都不存在，当前节点就是尾节点
  return rightTail ?? leftTail ?? root
}

为什么返回尾节点

这个返回值是整个递归算法的核心关键，目的是给上层节点提供 “连接的锚点”：

上层节点需要知道自己左子树展开后的最后一个节点是谁，才能把这个节点的 right 指针指向自己的右子树（完成 “左子树→右子树” 的连接）；

一个例子

还是用之前的二叉树片段：

text

  2
 / \
3   4

当处理节点 2 的左子树（节点 3）时：

节点 3 没有左右子树，展开后就是它自己，所以 “左子树展开后的尾节点” 就是 3；

当处理节点 2 时，递归调用
text
```
flatten(root.left)
```
（也就是处理节点 3），返回的
text
```
leftTail
```
就是 3（节点 3 是左子树展开后的尾节点）；

再看处理节点 2 的完整过程：

先递归处理左子树（3），返回尾节点 3；
再递归处理右子树（4），返回尾节点 4；
此时leftTail（3）存在，所以执行：
- 3.right = 2.right（也就是 4）→ 把左子树尾节点连到右子树的头；
- 2.right = 2.left（也就是 3）→ 把当前节点连到左子树的头；
- 2.left = null；
最后返回右子树的尾节点 4（这就是节点 2 整个子树展开后的尾节点）。

return rightTail ?? leftTail ?? root; 保证返回尾节点

头插法

采用头插法构建链表，也就是从节点 6 开始，在 6 的前面插入 5，在 5 的前面插入 4，依此类推。

为此，要按照 6→5→4→3→2→1 的顺序访问节点。如何遍历这棵树，才能实现这个顺序？

按照右子树 - 左子树 - 根的顺序 DFS 这棵树。

var flatten = function (root) {
  let head = null
  function dfs(node) {
    if (node === null) {
      return
    }
    dfs(node.right)
    dfs(node.left)
    node.left = null
    node.right = head // 头插法，相当于链表的 node.next = head
    head = node // 现在链表头节点是 node
  }
  dfs(root)
}

Morris 算法