114_flatten_binary_tree_to_linked_list

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

代码参考：

package main

import "fmt"

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Right = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 5}
    flatten(root)

    fmt.Println(root)
    fmt.Println(root.Right)
    fmt.Println(root.Right.Right)
    fmt.Println(root.Right.Right.Right)
    fmt.Println(root.Right.Right.Right.Right)
}

// 原地展开，不能先序遍历建新树
//    1
//   / \
//  2   5

// 1
//  \
//   2
//    \
//     5
func flatten(root *TreeNode) {
    if root == nil {
        return
    }
    if root.Left == nil && root.Right == nil {
        return
    }

    flatten(root.Left)
    flatten(root.Right)

    if root.Left != nil {
        lastNode := root.Right
        root.Right = root.Left // 把左子树挪到右子树上

        cur := root
        for cur.Right != nil {
            cur = cur.Right
        }
        cur.Right = lastNode // 把旧右子树接到新右子树
        root.Left = nil      // 清空左子树
    }
}