leetcode114 二叉树展开为链表

题目

给你二叉树的根结点 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 = nil
		prev.Right = cur
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25