114. 二叉树展开为链表（JS实现）

矫情吗；* 2023-02-21 09:14 54阅读 0赞

## 1 题目 ##

> 给定一个二叉树，原地将它展开为一个单链表。  
> 例如，给定二叉树  
> 1  
> /  
> 2 5  
> / \\  
> 3 4 6  
> 将其展开为：  
> 1  
>   
> 2  
>   
> 3  
>   
> 4  
>   
> 5  
>   
> 6

## 2 思路 ##

**这道题我的思路比较直接，首先前序遍历树，然后用next指针链接每个节点，随后修改原来right指针，题解的方法比较巧妙，对树进行变形的后序遍历，遍历顺序是右子树->左子树->根节点**  
例如，我们依次遍历 6 5 4 3 2 1，然后每遍历一个节点就将当前节点的右指针更新为上一个节点，`6 <- 5 <- 4 3 2 1`

1
       / \
      2   5
     / \   \
    3   4   6

## 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 stack = [];
      let p = root;
      let link = { };
      let linkHead = link;
    
      while (p || stack.length > 0) { 
        while (p) { 
          link.next = p;
          link = link.next;
          stack.push(p);
          p = p.left;
        }
    
        p = stack.pop();
        p = p.right;
      }
    
      link = linkHead.next;
      while(link) { 
        root.right = link.next;
        root.left = null;
        root = root.right;
        link = link.next;
      }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode114. 二叉树展开为链表

给定一个二叉树，原地将它展开为链表。例如，给定二叉树 1 / \\ 2 5 / \\ \\ 3 4 6 将其展开为： 1 \\ 2 \\

灰太狼/ 2023年07月03日 02:48/ 0 赞/ 18 阅读

相关 114. 二叉树展开为链表

[114. 二叉树展开为链表][114.] 给定一个二叉树，[原地][Link 1]将它展开为一个单链表。例如，给定二叉树 1 / \

r囧r小猫/ 2023年03月04日 08:07/ 0 赞/ 10 阅读

相关 114. 二叉树展开为链表（JS实现）

1 题目 > 给定一个二叉树，原地将它展开为一个单链表。 > 例如，给定二叉树 > 1 > / > 2 5 > / \\ > 3 4 6 >

矫情吗；*/ 2023年02月21日 09:14/ 0 赞/ 55 阅读

相关 114. 二叉树展开为链表

题目来源 [114. 二叉树展开为链表][114.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

r囧r小猫/ 2022年12月22日 10:00/ 0 赞/ 177 阅读

相关 LeetCode 114. 二叉树展开为链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

蔚落/ 2022年11月05日 08:51/ 0 赞/ 147 阅读

相关（js）leetcode 114. 二叉树展开为链表

题目： > 给你二叉树的根结点 root ，请你将它展开为一个单链表： > > 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个

小灰灰/ 2022年11月05日 08:48/ 0 赞/ 144 阅读

相关 114. 二叉树展开为链表

> 给你二叉树的根结点 root ，请你将它展开为一个单链表(并不是链表) > > 展开后的单链表应该与二叉树先序遍历顺序相同。![watermark_type_ZmFu

刺骨的言语ヽ痛彻心扉/ 2022年10月08日 02:25/ 0 赞/ 114 阅读

相关 Leetcode 114. 二叉树展开为链表

题目给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指

傷城~/ 2022年08月28日 02:50/ 0 赞/ 136 阅读

相关 LeetCode 114. 二叉树展开为链表

给定一个二叉树，原地将它展开为链表。例如，给定二叉树 1 / \\ 2 5 / \\ \\ 3

青旅半醒/ 2021年12月03日 16:17/ 0 赞/ 189 阅读

相关 leetcode:114. 二叉树展开为链表(java)

给定一个二叉树，[原地][Link 1]将它展开为链表。例如，给定二叉树 1 / \ 2 5 / \ \ 3

深碍√TFBOYSˉ_/ 2021年09月28日 11:52/ 0 赞/ 199 阅读