力扣链接：114.二叉树展开为链表

难度：⭐⭐

✏️ 方法一：

解题关键词：二叉树、链表

解题思路：使用前序遍历将节点都收集到一个数组中，之后将每个节点的左节点设置为空，将右节点设置为数组中下一个元素。

var flatten = function(root) {
    const list = [];

    // 前序遍历将每个节点都加入到数组中
    preOrderTraversal(root, list);
    const size = list.length;
    // 循环，将每个节点的左节点设置为空，将右节点设置为数组中下一个元素
    for (let i = 1; i < size; i++) {
        const prev = list[i - 1], cur = list[i];
        prev.left = null;
        prev.right = cur;
    }
};

// 递归前序遍历
const preOrderTraversal = (root, list) => {
    if (root != null) {
        list.push(root);
        preOrderTraversal(root.left, list);
        preOrderTraversal(root.right, list);
    }
}

✏️ 方法二：

解题关键词：二叉树、巧妙方法

解题思路：因为前序遍历，左子树中最右边的节点是右子树的前驱节点，所以我们将前驱节点的 right 指向右子树，然后将当前处理的节点左子树设置为空，右子树设置为左子树，然后继续下一个节点，即继续处理当前节点的右边节点。

function flatten(root: TreeNode | null): void {
  let cur = root

  while (cur !== null) {
    // 如果当前节点的左子树为空，那么符合条件，不处理
    if (cur.left !== null) {
      // 找到左子树中最右边的节点，即前驱节点
      let leftRight = cur.left
      while (leftRight.right) {
        leftRight = leftRight.right
      }

      // 将前驱节点的右子树设置为当前处理节点的右子树
      leftRight.right = cur.right

      // 将当前节点的右子树设置为左子树
      cur.right = cur.left
      // 将原来的左子树设置为空
      cur.left = null
    }

    // 继续处理下一个节点
    cur = cur.right
  }
};