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) 额外空间）展开这棵树吗？

核心思想

空间On解法：递归

1. 先递归处理左子树和右子树，将它们各自展开为链表。
2. 将展开后的左子树链表移到当前节点的右侧。
3. 找到左子树链表的最后一个节点（末尾）。
4. 将展开后的右子树链表附加到这个末尾节点。
5. 处理左子树为空的情况（直接保留右子树）。

• 递归到节点 2：先展开左子树（3）和右子树（4），然后将左子树（3）移到右侧，再找到末尾（3），附加右子树（4），得到 2 -> 3 -> 4。

• 递归到节点 1：左子树（2 -> 3 -> 4）移到右侧，找到末尾（4），附加右子树（5 -> 6），得到 1 -> 2 -> 3 -> 4 -> 5 -> 6。

空间O1解法：Morris遍历+前驱节点连接

Morris 遍历是一种 不使用递归或栈的中序遍历方法；

• 在本题中稍作修改，用于将每个节点的左子树插入到当前节点和右子树之间；
• 每次处理当前节点时：
  • 如果存在左子树，则找到左子树的最右节点（前驱节点）；
  • 将该前驱节点的右指针指向当前节点的右子树；
• 然后将当前节点的右指针指向左子树，并清空左指针；
• 最终整棵树变成一个“只有右孩子”的链表结构。

代码

时间On，空间On

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    // 递归，直接把左孩子 变为 右孩子，右孩子变成 左孩子的 右孩子
    if root == nil {
        return 
    }
    flatten(root.Left)
    flatten(root.Right)

    rightSub := root.Right
 // 将左子树移到右侧，并清空左指针
    root.Right = root.Left
    root.Left = nil

    // 要找到现在最右叶子，把 rightSub接上去
    curNode := root
    for curNode.Right != nil {
        curNode = curNode.Right
    }
    curNode.Right = rightSub
}

空间O1做法：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    // Morris 将每个节点左节点 插入到 当前节点 和 右节点 之间
    cur := root
    for cur != nil {
        // 如果有左子树，就要移植；没有左跳过
        if cur.Left != nil {
            // 当前结点的 右节点
            listNxt := cur.Right
            // 现在要找到 前驱节点，也就是 左子树 最右节点
            prev := cur.Left
            for prev.Right != nil {
                prev = prev.Right
            }
            prev.Right = listNxt 
            cur.Right = cur.Left
            cur.Left = nil // 别忘了左节点为空
        }
        cur = cur.Right
    }
}