114.M 二叉树展开为链表

Problem: 114. 二叉树展开为链表

思路

思路1：先递归收集所有节点，然后再调整节点的左右指针。

思路2：通过迭代法收集所有节点，然后再调整节点的左右指针。

思路3：用迭代法一边收集节点，一边调整左右指针。这么做的前提是：需要提前把右子节点入栈，以免丢失右子树的信息。

Code

代码1：

func flattenV1(root *TreeNode) {
	nodes := helperV1(root)
	for i := 0; i < len(nodes)-1; i++ {
		nodes[i].Right = nodes[i+1]
		nodes[i].Left = nil
	}
}

func helperV1(root *TreeNode) []*TreeNode {
	if root == nil {
		return nil
	}

	nodes := []*TreeNode{root}
	nodes = append(nodes, helperV1(root.Left)...)
	nodes = append(nodes, helperV1(root.Right)...)
	return nodes
}

代码2：

func flattenV2(root *TreeNode) {
	nodes := helperV2(root)
	for i := 0; i < len(nodes)-1; i++ {
		nodes[i].Right = nodes[i+1]
		nodes[i].Left = nil
	}
}

func helperV2(root *TreeNode) []*TreeNode {
	var stack []*TreeNode
	var nodes []*TreeNode
	for root != nil || len(stack) > 0 {
		for root != nil {
			nodes = append(nodes, root)
			stack = append(stack, root)
			root = root.Left
		}

		root = stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		root = root.Right
	}
	return nodes
}

代码3：

func flatten(root *TreeNode) {
	if root == nil {
		return
	}

	stack := []*TreeNode{root}
	var pre *TreeNode
	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		if pre != nil {
			pre.Left = nil
			pre.Right = cur
		}

        // 先入栈右子节点
		if cur.Right != nil {
			stack = append(stack, cur.Right)
		}

		if cur.Left != nil {
			stack = append(stack, cur.Left)
		}

		pre = cur
	}
}