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;
    };
相关文章
|
12天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
15天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
38 5
|
18天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
24 0
|
23天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
23天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
1月前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
1月前
|
算法 索引
经典算法之链表篇
经典算法之链表篇
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
18 1
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
32 0
下一篇
无影云桌面