1. 题目描述

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

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：
image.png

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

示例 2：

  1. 输入：root = []
  2. 输出：[]

示例 3：

  1. 输入：root = [0]
  2. 输出：[0]

提示：

  • 树中结点数在范围 [0, 2000] 内

  • -100 <= Node.val <= 100


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

    2. 解题思路

    题目中也说了，展开后的单链表与二叉树 先序遍历 顺序相同，所以我们可以先对二叉树进行先序遍历，然后将遍历的结果置位一条链表。这个链表相当于左子节点都是null，右子节点都是二叉树的值的二叉树。

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。

  • 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n。

    3. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val, left, right) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.left = (left===undefined ? null : left)
    6. *     this.right = (right===undefined ? null : right)
    7. * }
    8. */
    9. /**
    10. * @param {TreeNode} root
    11. * @return {void} Do not return anything, modify root in-place instead.
    12. */
    13. var flatten = function(root) {
    14.   // 前序遍历
    15.   const fn = (root) => {
    16.       if(!root){
    17.           return 
    18.       }
    19.       res.push(root)
    20.       fn(root.left)
    21.       fn(root.right)
    22.   }
    24.   let res = []
    25.   fn(root)
    26.   for(let i = 0; i < res.length - 1; i++){
    27.       res[i].left = null
    28.       res[i].right = res[i + 1]
    29.   }
    30. };

    4. 提交结果

    image.png