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

小灰灰 2022-11-05 08:48 144阅读 0赞

### 题目： ###

> 给你二叉树的根结点 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

### 思路： ###

> 采用后序遍历
> 
> 1. 将 root 的左子树和右子树拉平
> 
> 2. 将 root 的右子树接到左子树下方，然后将整个左子树作为右子树

### 代码实现： ###

/**
     * 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) {
        if(root == null) return;
    
        flatten(root.left);
        flatten(root.right);
    
        // 1. 左右子树已经被拉平成一条链表
        let left = root.left;
        let right = root.right;
    
        // 2. 将左子树设为右子树
        root.left = null;
        root.right = left;
    
        // 3. 将原先的右子树接到当前右子树的末端
        let p = root;
        while(p.right != null) {
            p = p.right;
        }
        p.right = right;
    };

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221023/8adacdb1c8584638a3701b5ab085f832.png