「leetCode」114-二叉树展开为链表⚡️

简介: 「leetCode」114-二叉树展开为链表⚡️

image.png

题目🦀


114. 二叉树展开为链表


难度中等


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


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


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


示例 1:


image.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) 额外空间)展开这棵树吗?


解题思路🌵


  • 先进行前序遍历,遍历出各个节点
  • 然后将节点依次放书数组中
  • 最后遍历数组,拼接链表


解题步骤🐂


  • 初始化list数组用来存放结点


  • 进行先序遍历,存放结点


  • 遍历结点,拼接为链表


源码🔥


/**
 * 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) {
        let list = []
        preTravel(root,list)
        for(let i=1;i<list.length;i++){
            const pre = null;
            const cur = list[i]
            list[i-1].left=pre;
            list[i-1].right=cur
        }
};
function preTravel(root,list){
    if(root){
        list.push(root)
        preTravel(root.left,list)
        preTravel(root.right,list)
    }
}

时间复杂度:O(n)


空间复杂度:O(n)


结束语🌞


image.png

那么鱼鱼的LeetCode算法篇的「leetCode」114-二叉树展开为链表⚡️就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步

相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
35 1
|
1月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
48 0
Leetcode第21题(合并两个有序链表)
|
1月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
19 2
|
1月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
16 2
|
1月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
15 2
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
19 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
14 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
16 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
16 0