/*
 * @lc app=leetcode.cn id=589 lang=golang
 *
 * [589] N 叉树的前序遍历
 */

// 2-2. 循环，把每一层倒着入栈
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func preorder(root *Node) (ans []int) {
	if root == nil {
		return
	}
	stack := []*Node{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ans = append(ans, node.Val)
		for i := len(node.Children) - 1; i >= 0; i-- {
			stack = append(stack, node.Children[i])
		}
	}
	return
}

// @lc code=end

// 2-1. 循环
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func preorder(root *Node) (ans []int) {
	stack := []*Node{}
	nextIndexMap := make(map[*Node]int)
	for root != nil || len(stack) > 0 {
		for root != nil {
			ans = append(ans, root.Val)
			stack = append(stack, root)

			if len(root.Children) == 0 {
				break
			}
			nextIndexMap[root] = 1
			root = root.Children[0]
		}

		root = stack[len(stack)-1]
		i := nextIndexMap[root]
		if i < len(root.Children) {
			nextIndexMap[root] = i + 1
			root = root.Children[i]
		} else {
			stack = stack[:len(stack)-1]
			root = nil
		}
	}
	return
}

// @lc code=end

// 1-2. 递归
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func preorder(root *Node) (ans []int) {
	var pre func(nodes []*Node)
	pre = func(nodes []*Node) {
		for i := 0; i < len(nodes); i++ {
			if nodes[i] != nil {
				ans = append(ans, nodes[i].Val)
				pre(nodes[i].Children)
			}
		}
	}
	pre([]*Node{root})
	return
}

// @lc code=end

// 1-1. 递归
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func preorder(root *Node) (ans []int) {
	var pre func(node *Node)
	pre = func(node *Node) {
		if node == nil {
			return
		}
		ans = append(ans, node.Val)
		for i := 0; node.Children != nil && i < len(node.Children); i++ {
			pre(node.Children[i])
		}
	}

	pre(root)
	return
}

// @lc code=end