2021-02-13 | 114. 二叉树展开为链表

客官°小女子只卖身不卖艺 2022-11-08 14:22 105阅读 0赞

### 1. 题目描述 ###

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

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

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

示例 1：  
![在这里插入图片描述][20210313224616282.png]

输入：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) 额外空间）展开这棵树吗？

### 2. 解题思路 ###

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

**复杂度分析：**

*  时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。
 *  空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n。

### 3. 代码实现 ###

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
    /** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */
    var flatten = function(root) { 
        // 前序遍历
        const fn = (root) => { 
            if(!root){ 
                return 
            }
            res.push(root)
            fn(root.left)
            fn(root.right)
        }
    
        let res = []
        fn(root)
        for(let i = 0; i < res.length - 1; i++){ 
            res[i].left = null
            res[i].right = res[i + 1]
        }
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210313224634232.png]

[20210313224616282.png]: /images/20221023/ac15cf7b680242ad9fadd7c9208ca2c6.png?
[20210313224634232.png]: /images/20221023/90a615d3cd3b438face42162ef47e214.png?