西安网站建设制作黑五类广告推广

题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

解析

注意下函数签名：
func flatten(root *TreeNode) {} // 注意没有返回值
这道题的题目中已经描述比较清晰了，告诉了和前序遍历相同，那么就意味先来一遍前序遍历，将遍历后的结果存起来，这里需要注意一下，之前是存到了一个[]int{}结构里，因为之前返回的是一个int数组，而这次要返回链表，所以要提前定义一个[]*TreeNode{}的结构，前序遍历完得到这个结构后，再来一个循环遍历这个数组，同时遍历这个数组的两个节点，将每个节点的left置为nil，right指向下一个节点就可以了

func flatten(root *TreeNode) {if root == nil {return}listNew := []*TreeNode{}stack := list.New()stack.PushBack(root)for stack.Len() > 0 {node := stack.Remove(stack.Back()).(*TreeNode)listNew = append(listNew, node)if node.Right != nil {stack.PushBack(node.Right)}if node.Left != nil {stack.PushBack(node.Left)}}for i := 1; i < len(listNew); i++ {prev, cur := listNew[i-1], listNew[i]prev.Left = nilprev.Right = cur}
}