记录小白学算法之-二叉树展开为链表

小弟学习技术忙，一大家子需人养，前年躺平今年卷，活到退休梦一场。

大家偏爱搞算法，计科出生也难懂，后浪推着前浪走，前浪努力才能不死在沙滩上。

躺平就是伪命题，除非家里有钱烧，今后努力学到死，孩子才能不饿死。

最近小弟偏爱学习，遂决定将自己的学习过程记录下来，也是日后能提醒自己 帮助自己，加油 平凡人

话不多说贴原题

114. 二叉树展开为链表

难度中等1113

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

进阶： 你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

从题目提取一些关键的节点处理信息

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

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

归纳一番 原先的左节点成了之前兄弟右边节点的 父节点，而自己本来的位置 成了null（并不是让你把节点删除了）

那我们需要做的就很明显了，第一 对树进行一次先序遍历 进行展开，第二 展开完成之后想办法将 左节点 变成 兄弟节点的 父亲节点。

第一步很简单，关键在于第二步想了两个办法，第一个用一个数组保存上前序遍历，然后遍历数组 操作树，但是这个多出来一个数组 空间复杂度不满足题目O(1)的要求

第二个是先办法 从底至上 左父右，没有用任何多余的空间，空间复杂度O(1)

完成 检验代码

function flatten(root: TreeNode | null): void {
    if(!root){
        return null
    }
    let pre = null
    // 从底至上交换节点
    function change(cur) {
        console.info(cur)
        // 先右 后左
        if (cur.right) {
            change(cur.right)
        }
        if (cur.left) {
            change(cur.left)
        }
        // 递归的话 最后读取的是左边的
        cur.right = pre
        cur.left = null
        // 先记录左边
        pre = cur
    }
    change(root)
};
复制代码