前端算法题解leetcode114二叉树展开为链表

目录
  • 正文
  • 解题思路-基础
    • 代码实现
  • 解题思路-进阶
    • 代码实现

正文

题目地址

给你二叉树的根结点 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) 额外空间）展开这棵树吗？

解题思路-基础

本题要求我们把二叉树拆成单链表，但是其实仍然是二叉树，只不过每个子树只有右子树。
最简单的办法就是前序遍历二叉树，将节点放入数组，然后遍历前序遍历获取到的节点数组，构造结果二叉树。

代码实现

function treeToList(root){
    const list = []
    function preorder(node){
        if(node === null){
            return
        }
        list.push(node)
        preorder(node.left)
        preorder(node.right)
    }
    preorder(root)
    return list
}
var flatten = function(root) {
    if(root === null){
        return null
    }
    const list = treeToList(root)
    for(let i = 1;i&lt;list.length;i++){
        list[i-1].left = null
        list[i-1].right = list[i]
    }
}

解题思路-进阶

上面的解题思路可以完成解题，但是没有达到本题进阶的要求：使用原地算法（O(1) 额外空间）展开这棵树。

想要达到进阶的要求，就只能使用常量的额外空间，这里其实我们可以借用一个 current 变量指向当前正在处理的节点，同样是前序遍历，每次把当前节点挂到 current 的右子树上，同时把 current 的左子树置为 null，防止出现循环引用，然后继续处理后续节点，这样当前序遍历完成，就把二叉树处理成了单链表状态。

代码实现

var flatten = function(root) {
    if(root === null){
        return null
    }
    let current = {}
    function preorder(node){
        if(node === null){
            return
        }
        current.left = null
        current.right = node
        current = current.right
        const left = current.left
        const right = node.right
        preorder(left)
        preorder(right)
    }
    preorder(root)
}

至此我们就完成了 leetcode-114-二叉树展开为链表，更多关于前端算法二叉树展开为链表的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 前端算法题解leetcode36-有效的数独示例

    前端算法题解leetcode36-有效的数独示例

    目录 题目 解题思路-分别处理 代码实现 解题思路-一次扫描判断所有 代码实现 题目 题目地址 请你判断一个 9 x 9 的数独是否有效.只需要 根据以下规则 ,验证已经填入的数字是否有效即可. 数字 1-9 在每一行只能出现一次. 数字 1-9 在每一列只能出现一次. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次.(请参考示例图) 注意: 一个有效的数独(部分已被填充)不一定是可解的. 只需要根据以上规则,验证已经填入的数字是否有效即可. 空白格用 '.' 表示. 示例 1:

  • 前端算法leetcode109题解有序链表转换二叉搜索树

    前端算法leetcode109题解有序链表转换二叉搜索树

    目录 题目 解题思路-基础 代码实现 解题思路-优化 代码实现 解题思路-进阶 代码实现 题目 题目地址 给定一个单链表的头节点  head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树. 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1. 示例 1: 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树.

  • LeetCode 题解 Swift 有效的完全平方数

    LeetCode 题解 Swift 有效的完全平方数

    目录 题目 方法一:使用内置的库函数 思路及解法 复杂度分析 方法二:暴力 思路及解法 代码 复杂度分析 方法三:二分查找 思路及解法 细节 代码 复杂度分析 题目 给定一个 正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 true,否则返回 false. 进阶:不要 使用任何内置的库函数,如 sqrt. 示例 1: 输入: num = 16 输出: true 示例 2: 输入: num = 14 输出: false 方法一:使用内置的库函数 思路及解法 根据完全平方数的性

  • 前端算法题解 leetcode50-Pow(x, n)

    目录 题目 解题思路-分情况讨论 代码实现 解题思路-分治 代码实现 题目 题目地址 实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn ). 示例 1: 输入: x = 2.00000, n = 10 输出: 1024.00000 示例 2: 输入: x = 2.10000, n = 3 输出: 9.26100 示例 3:. 输入: x = 2.00000, n = -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 提示: -100.0

  • 前端算法题解leetcode49-字母异位词分组

    目录 题目 解题思路 代码实现 题目 题目地址 给你一个字符串数组,请你将 字母异位词 组合在一起.可以按任意顺序返回结果列表. 字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次. 示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],[

  • LeetCode 刷题 Swift 两个数组的交集

    LeetCode 刷题 Swift 两个数组的交集

    目录 题目 方法一:两个集合 思路及解法 代码 复杂度分析 方法二:排序 + 双指针 思路及解法 代码 复杂度分析 题目 给定两个数组 nums1 和 nums2,返回 它们的交集 .输出结果中的每个元素一定是 唯一 的.我们可以 不考虑输出结果的顺序 . 示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4] 解释: [4,9] 也是可

  • 前端算法题解leetcode114二叉树展开为链表

    前端算法题解leetcode114二叉树展开为链表

    目录 正文 解题思路-基础 代码实现 解题思路-进阶 代码实现 正文 题目地址 给你二叉树的根结点 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

  • C++实现LeetCode(114.将二叉树展开成链表)

    [LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展开成链表 Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2   5 / \   \ 3   4   6 The flattened tree should look like:    1 \ 2 \ 3 \ 4 \ 5 \ 6 click to show hints

  • JavaScript前端学算法题解LeetCode最大重复子字符串

    JavaScript前端学算法题解LeetCode最大重复子字符串

    目录 最大重复子字符串 解题思路 知识点 这是LeetCode的第1668题:最大重复子字符串 最大重复子字符串 给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word 的 重复值为 k .单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值.如果 word 不是 sequence 的子串,那么重复值 k 为 0 .给你一个字符串 sequence 和 word ,请你返回

  • go语言算法题解二叉树的最小深度

    目录 题目: 说明: 解法: 题目: 给定一个二叉树,找出其最小深度. 最小深度是从根节点到最近叶子节点的最短路径上的节点数量. 说明: 叶子节点是指没有子节点的节点. 解法: func minDepth(root *TreeNode) int { if root == nil { return 0 } minDepth := math.MaxInt64 var dfs func(node *TreeNode, depth int) dfs = func(node *TreeNode, dept

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • Java 数据结构与算法系列精讲之单向链表

    Java 数据结构与算法系列精讲之单向链表

    目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表

随机推荐