package flattenbinarytreetolinkedlist

import . "gitee.com/dllearn/geektime-algorithm-learn/structures"

// 114. 二叉树展开为链表
// https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

// 根 - 左 - 右
var head *TreeNode
var pre *TreeNode

func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	head = &TreeNode{}
	pre = head
	dfs(root)
	root.Left = nil
	root.Right = head.Right.Right
	return
}

func dfs(node *TreeNode) {
	if node != nil {
		r := &TreeNode{Val: node.Val}
		pre.Right = r
		pre = r
		dfs(node.Left)
		dfs(node.Right)
	}
	return
}