给你二叉树的根结点 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) {
if root == nil {
return
}
start := &TreeNode{Val: 0}
temp := start
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
temp.Right = &TreeNode{Val: node.Val}
temp = temp.Right
dfs(node.Left)
dfs(node.Right)
}
dfs(root)
root = start.Right
}验证的时候说错了，我专门构造了那个输入，本地的输出和答案是一样的，提交的输出居然和本地的不一样
官方解法：
1.前序遍历
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 {
var list []*TreeNode
if root != nil {
list = append(list, root)
list = append(list, preorderTraversal(root.Left)...)
list = append(list, preorderTraversal(root.Right)...)
}
return list
}通过迭代实现前序遍历
func flatten(root *TreeNode) {
var list []*TreeNode
var stack []*TreeNode
node := root
for node != nil || len(stack) > 0 {
for node != nil {
list = append(list, node)
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack)-1]
node = node.Right
stack = stack[:len(stack)-1]
}
for i := 1; i < len(list); i++ {
prev, curr := list[i-1], list[i]
prev.Left, prev.Right = nil, curr
}
}2.前序遍历和展开同步进行
func flatten(root *TreeNode) {
if root == nil {
return
}
stack := []*TreeNode{root}
var prev *TreeNode
for len(stack) > 0 {
curr := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if prev != nil {
prev.Left, prev.Right = nil, curr
}
left, right := curr.Left, curr.Right
if right != nil {
stack = append(stack, right)
}
if left != nil {
stack = append(stack, left)
}
prev = curr
}
}3.寻找前驱节点
func flatten(root *TreeNode) {
curr := root
for curr != nil {
if curr.Left != nil {
next := curr.Left
predecessor := next
for predecessor.Right != nil {
predecessor = predecessor.Right
}
predecessor.Right = curr.Right
curr.Left, curr.Right = nil, next
}
curr = curr.Right
}
}