114. 二叉树展开为链表

题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]

输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [0]

输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

出处：LeetCode

解法一：前序遍历

思路

前序遍历二叉树，将遍历结果保存在数组中，再将数组中的节点连接起来。

实现

function flatten(root: TreeNode | null): void {
  const nodes: TreeNode[] = [];
  const preorder = (node: TreeNode | null) => {
    if (node === null) {
      return;
    }
    nodes.push(node);
    preorder(node.left);
    preorder(node.right);
  };
  preorder(root);
  for (let i = 1; i < nodes.length; i++) {
    const prev = nodes[i - 1];
    const curr = nodes[i];
    prev.left = null;
    prev.right = curr;
  }
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法二：前序遍历（原地）

思路

前序遍历二叉树，将前一个节点的左子节点指向 null，右子节点指向当前节点。

实现

function flatten(root: TreeNode | null): void {
  let prev: TreeNode | null = null;
  const preorder = (node: TreeNode | null) => {
    if (node === null) {
      return;
    }
    if (prev !== null) {
      prev.left = null;
      prev.right = node;
    }
    prev = node;
    const right = node.right;
    preorder(node.left);
    preorder(right);
  };
  preorder(root);
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$