114. 二叉树展开为链表

题目描述：

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

---

解题分析及思路：

二叉树的前序遍历顺序是按照根节点、左子树、右子树的次序访问各节点。

在进行展开操作时，有两个情况需要考虑：

• 如果一个节点的左子节点为空，那么无需展开该节点。
• 如果一个节点的左子节点不为空，那么在其左子树中最右边的节点被访问后，再访问该节点的右子节点。

为了找到当前节点的前驱节点，我们可以采取以下步骤：

• 如果当前节点的左子节点不为空，就在其左子树中找到最右边的节点，它将成为当前节点的前驱节点。
• 将当前节点的右子节点赋给前驱节点的右子节点。
• 然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。

这样，针对当前节点的处理完成后，继续处理链表中的下一个节点，直到所有节点都被处理完毕。

func flatten(root *TreeNode) {
	curr := root
	for curr != nil {
		if curr.Left != nil {
			pre := curr.Left
			for pre.Right != nil {
				pre = pre.Right
			}
			pre.Right = curr.Right
			curr.Left, curr.Right = nil, curr.Left
		}
		curr = curr.Right
	}
}

复杂度：

• 时间复杂度：O(N)，其中 N 是树中的节点个数
• 空间复杂度：O(1)

执行结果：

• 执行耗时:2 ms,击败了37.13% 的Go用户
• 内存消耗:2.7 MB,击败了87.01% 的Go用户