面试经典 114. 二叉树展开为链表

最近工作越来越难找，裁员越来越懂了，焦虑的睡不着，怎么办呢，只能刷面试题，卷死你们
今天这个题目没刷过，我思考了半天才只能用暴力，后来苦思冥想才想出来简单的方法，废话不多说，上链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150
做这个题目之前，首先你要知道两个知识点：
- 什么是二叉树？
- 什么是先序遍历？
先回答第一个问题，什么是二叉树？这是一个数据结构，是一种常见的树状数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点，如上图。
了解什么是二叉树，才能回答第二问题，什么是先序遍历？首先这是一种遍历整个二叉树的方法，先序遍历：按照左子树 -> 根节点 -> 右子树的顺序遍历二叉树
好了，了解了这两个基础知识，现在就来解决这道题。
这道题目的是让我们把一颗树转变成一个单向链表
这不简单，最暴力的方法就是用数组，把先序遍历的节点都存储起来，然后再通过遍历数组把他们都连接在一起不就行了吗，代码如下：

func flatten(root *TreeNode)  {list := preorderTraversal(root)//遍历整个数组，将树变成单向链表for i := 1; i < len(list); i++ {prev, curr := list[i-1], list[i]prev.Left, prev.Right = nil, curr}
}

//将节点按照先序遍历的方式存储到数组中
func preorderTraversal(root *TreeNode) []*TreeNode {list := []*TreeNode{}if root != nil {list = append(list, root)list = append(list, preorderTraversal(root.Left)...)list = append(list, preorderTraversal(root.Right)...)}return list
}

ok，运行倒是成功了，但是这个效率可太难了，面试的时候，遇到这个题，只用这种做法肯定不成，怎么办呢？
我仔细想了想有两个优化方向
- 时间方面，我希望只遍历一遍整个树就能解决这个问题
- 空间方面，我希望空间复杂度为o(1) 就能解决
方向确定好了，怎么办呢？
通过我聪明的脑瓜子，转了又转，我想到了
先序遍历是根左右，相当于每次右子树都在后面，那我们可以把右子树，放到左子树最右边那个节点下面，并且当前根节点根据需求改造就行。
这么讲有点抽象，我们通过图来举例，假设如示例1：
如果我们只关注当前节点 1 的话，我们需要做三个操作
- 找到左子树最右的节点
- 将右子树放到左子树最右的节点的右边
- 将左子树放到当前节点的右边
结果就如下图：
是不是发现突然好像解决了一大半了
ok，我们继续，运行到 2 节点，继续上面的三个操作，结果如下：
基本上，我们就变成了一个单向链表，剩下的节点就重复的遍历下去，直至结束
代码如下：

func Solution114(root *TreeNode)  {//遍历整个二叉树for root != nil{//如果有左子树if root.Left != nil{//找到左子树的最右节点next := root.Leftpre := nextfor pre.Right != nil{pre = pre.Right}//将原来的右子树接到左子树的最右节点pre.Right = root.Rightroot.Left, root.Right = nil, next}//继续下一个节点root = root.Right}
}