JS算法-二叉树展开转为链表

简介: JS算法-二叉树展开转为链表

题目


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


  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入: root = [1,2,5,3,4,null,6]
输出: [1,null,2,null,3,null,4,null,5,null,6]

根据以上题目要求,我想到了以下解法


解题思路


第一种


对于这种题目,我脑海中第一个浮现出来的就是递归这种方式,所以我们这里先采用递归的方式来对上述算法题求解,通过递归从最小的节点开始进行慢慢推平,推平到全局,由点成面,首先我们对root数组的最左侧节点的最底部开始进行向上遍历,然后将当前遍历中节点的左节点直接替换掉右节点,然后在从最左侧节点向下查找,如果找到没有右节点的数据,则将上一个右节点直接放到当前节点的后面,这样一个节点就完成了,然后进行遍历父节点,我们需要将当前的左节点全部拼接在父节点的右节点上并依次向右节点进行遍历,如果发现右侧没有节点那么就将之前的右节点放在当前节点的右边,这样就可以得到一个新的数组,然后在依次进行递归让数据向上传递,就可以获得一个完整的单链表数

var flatten = function(root) {
    if (!root) return;
    flatten(root.left);
    flatten(root.right);
    const right = root.right;
    root.right = root.left;
    root.left = null;
    let p = root;
    while (p.right) {
        p = p.right;
    }
    p.right = right;
};


第二种


我们首先定义了两个变量,list用于存放遍历的节点,stack用于存放遍历的路径。接着定义了一个变量node,默认值root,用于存放当前遍历的节点。然后在while循环中,先判断node是否存在,若存在,则将它加入list和stack 数组中。然后将node的左子节点赋值给node,继续遍历左子节点。若node 不存在,即当前的子树遍历完了,则将 stack 中最后一个元素弹出,并将其右子节点赋值给 node,继续遍历右子节点。若node 不存在了且stack数组为空时,说明遍历完成,此时list数组中存放的就是展开后的节点。最后将每个节点的左子节点设为null,将右子节点设为前一个节点,即可将二叉树展开成链表

   var flatten = function (root) {
      const list = [];
      const stack = [];
      let node = root;
      while (node || stack.length) {
        while (node) {
          list.push(node);
          stack.push(node);
          node = node.left;
        }
        node = stack.pop();
        node = node.right;
      }
      const size = list.length;
      for (let i = 1; i < size; i++) {
        const prev = list[i - 1], curr = list[i];
        prev.left = null;
        prev.right = curr;
      }
      return list;
    };
相关文章
|
3天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
8 0
|
2月前
|
算法 JavaScript 前端开发
第一个算法项目 | JS实现并查集迷宫算法Demo学习
本文是关于使用JavaScript实现并查集迷宫算法的中国象棋demo的学习记录,包括项目运行方法、知识点梳理、代码赏析以及相关CSS样式表文件的介绍。
第一个算法项目 | JS实现并查集迷宫算法Demo学习
|
27天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
16 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
27天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
17 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
1月前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
【二叉树】—— 算法题
|
27天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
22 0
|
3月前
|
JavaScript 算法 前端开发
JS算法必备之String常用操作方法
这篇文章详细介绍了JavaScript中字符串的基本操作,包括创建字符串、访问特定字符、字符串的拼接、位置查找、大小写转换、模式匹配、以及字符串的迭代和格式化等方法。
JS算法必备之String常用操作方法
|
3月前
|
JavaScript 算法 前端开发
JS算法必备之Array常用操作方法
这篇文章详细介绍了JavaScript中数组的创建、检测、转换、排序、操作方法以及迭代方法等,提供了数组操作的全面指南。
JS算法必备之Array常用操作方法
|
3月前
|
算法 JavaScript 前端开发
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
251 1
|
3月前
|
JavaScript 算法 前端开发
"揭秘Vue.js的高效渲染秘诀:深度解析Diff算法如何让前端开发快人一步"
【8月更文挑战第20天】Vue.js是一款备受欢迎的前端框架,以其声明式的响应式数据绑定和组件化开发著称。在Vue中,Diff算法是核心之一,它高效计算虚拟DOM更新时所需的最小实际DOM变更,确保界面快速准确更新。算法通过比较新旧虚拟DOM树的同层级节点,递归检查子节点,并利用`key`属性优化列表更新。虽然存在局限性,如难以处理跨层级节点移动,但Diff算法仍是Vue高效更新机制的关键,帮助开发者构建高性能Web应用。
67 1