刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你二叉树的根结点 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) 额外空间）展开这棵树吗？

思路

原地修改指针指向

首先是比较简单容易想到的模拟遍历过程的方法

先序遍历我们肯定都能写出来，这个很简单。
但是如果把其他的点加上一起思考可能会乱，所以一般建议可以先把先序遍历写出来作为一个基底，再去改动会更加清晰，也更容易发现问题。

// 先序遍历
res := []int{}
func dfs(root *TreeNode) {
	if root == nil {
		return
	}
    res := append(res, root.Val)
    if root.Left != nil {
		dfs(root.Left)
	}
	if root.Right != nil {
		dfs(root.Right)
	}
}

比如这道题，就会比较容易发现

如果我们直接原地修改指针的指向，把左子树的节点指向右子树，那么会造成后续右子树节点的不可达

那就换个方式，既然正向会影响后面的节点，那我们就从后往前串联，就不会影响了
所以思路就变成了

先右再左最后根的遍历顺序，从后往前一个个节点串联

树旋转

首先感谢原作者的题解，这个方法很妙，大家可以移步看：原作者答案

我这里只做简单介绍：
大家可以看这个图，我们知道题中所谓的展开其实就是按先序遍历排序，那么反映到树的结构图上

• 其实就是将左子树移到右子树的位置
• 将右子树移到整个左子树的后面
• 子树中的左右子树也适用这个过程
  

这里贴一张原作者的效果示意图

建议在纸上自己画一下，其实很容易理解

这个思路很是巧妙，不禁让人拍案叫绝～

代码

原地修改指向

func flatten(root *TreeNode) {
	var pre *TreeNode
	if root == nil {
		return
	}
	if root.Right != nil {
		flatten(root.Right)
	}
	if root.Left != nil {
		flatten(root.Left)
	}
	root.Right = pre
	root.Left = nil
	pre = root
}

旋转

func flatten(root *TreeNode) {
	for root != nil {
		// 左子树为 nil，无需旋转，直接考虑下一个节点
		if root.Left == nil {
			root = root.Right
		} else {
			// 找左子树最右边的节点，才是root右子树应该拼接的位置
			pre := root.Left
			for pre.Right != nil {
				pre = pre.Right
			}
			// 将原来的右子树接到左子树的最右边节点
			pre.Right = root.Right
			// 将左子树插入到右子树的地方
			root.Right = root.Left
			root.Left = nil
			// 考虑下一个节点
			root = root.Right
		}
	}
}