// 1
  
44.二叉树的前序遍历(opens new window)
package main

import (
	"container/list"
	"fmt"
)

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//方法1:递归法

func preorderTraversal1(root *TreeNode) []int {
	res := make([]int, 0)
	var traversal func(node *TreeNode) //定义一个函数变量
	traversal = func(node *TreeNode) {
		if node == nil {
			return //遍历到空结点返回上一层
		}
		//前序遍历
		//中
		res = append(res, node.Val)
		//左
		traversal(node.Left) //递归调用
		//右
		traversal(node.Right) //递归调用
	}
	traversal(root)
	return res
}

// 方法2:迭代法 注意"container/list"的使用
func preorderTraversal2(root *TreeNode) []int {
	ans := []int{}

	if root == nil { //保证根结点不为空
		return ans
	}

	st := list.New()  //创建一个链表（实现栈的功能）
	st.PushBack(root) //根结点入栈 使用 PushBack() 在链表尾部插入元素

	for st.Len() > 0 { //st.Len()获取链表的长度
		node := st.Remove(st.Back()).(*TreeNode) //移除最后一个结点（栈顶元素出栈），最后转换类型
		ans = append(ans, node.Val)              //将最后一个结点加入结果集中
		if node.Right != nil {
			st.PushBack(node.Right) //先插入该节点的右孩子
		}
		if node.Left != nil {
			st.PushBack(node.Left) //再插入该节点的左孩子
		}
	}
	return ans
}
func main() {
	//k=3
	node1, node2, node3, node4 := TreeNode{1, nil, nil}, TreeNode{2, nil, nil}, TreeNode{7, nil, nil}, TreeNode{8, nil, nil}
	//k=2
	node5, node6 := TreeNode{4, &node1, &node2}, TreeNode{6, &node3, &node4}
	//k=1
	node7 := TreeNode{5, &node5, &node6}
	res1 := preorderTraversal1(&node7)
	res2 := preorderTraversal2(&node7)
	fmt.Printf("res1: %v
", res1) //res1: [5 4 1 2 6 7 8]
	fmt.Printf("res2: %v
", res2) //res2: [5 4 1 2 6 7 8]

}

// 145.二叉树的后序遍历(opens new window)
package main

import (
	"container/list"
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 方法一：递归法
func postorderTraversal1(root *TreeNode) []int {
	res := []int{}
	var traversal func(node *TreeNode)
	traversal = func(node *TreeNode) {
		if node == nil {
			return
		}
		//后序遍历
		//左
		traversal(node.Left)
		//后
		traversal(node.Right)
		//中
		res = append(res, node.Val)
	}
	traversal(root)
	return res
}

// 方法二：迭代法
// 思路：前序遍历是中左右，先变为中右左，然后反转数组为左右中，即为后序遍历
func postorderTraversa2(root *TreeNode) []int {
	stack := list.New()   //用一个双向链表模拟栈
	res := make([]int, 0) //存放结果集
	if root == nil {      //排除二叉树为空的情况
		return res
	}
	stack.PushBack(root)  //根结点首先入栈
	for stack.Len() > 0 { //依次对二叉树的其他所有结点进行入栈出栈
		//思路：栈顶结点先从栈中弹出并加入结果集中，然后在栈中先放入该结点的左孩子，再放入右孩子
		val := stack.Remove(stack.Back()).(*TreeNode)
		res = append(res, val.Val)
		if val.Left != nil {
			stack.PushBack(val.Left)
		}
		if val.Right != nil {
			stack.PushBack(val.Right)
		}

	}
	for i, j := 0, len(res)-1; i < len(res)/2; i++ { //反转切片
		res[i], res[j] = res[j], res[i]
		j--
	}
	return res
}

func main() {
	//k=3
	node1, node2, node3, node4 := TreeNode{1, nil, nil}, TreeNode{2, nil, nil}, TreeNode{7, nil, nil}, TreeNode{8, nil, nil}
	//k=2
	node5, node6 := TreeNode{4, &node1, &node2}, TreeNode{6, &node3, &node4}
	//k=1
	node7 := TreeNode{5, &node5, &node6}
	res1 := postorderTraversal1(&node7)
	fmt.Printf("res: %v
", res1) //res1: [1 2 4 7 8 6 5]
	res2 := postorderTraversa2(&node7)
	fmt.Printf("res2: %v
", res2) //res2: [1 2 4 7 8 6 5]
}

// 94.二叉树的中序遍历
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	res := []int{}
	var traversal func(node *TreeNode)
	traversal = func(node *TreeNode) {
		if node == nil {
			return
		}
		//中序遍历
		//左
		traversal(node.Left)
		//中
		res = append(res, node.Val)
		//后
		traversal(node.Right)

	}
	traversal(root)
	return res
}
func main() {
	//k=3
	node1, node2, node3, node4 := TreeNode{1, nil, nil}, TreeNode{2, nil, nil}, TreeNode{7, nil, nil}, TreeNode{8, nil, nil}
	//k=2
	node5, node6 := TreeNode{4, &node1, &node2}, TreeNode{6, &node3, &node4}
	//k=1
	node7 := TreeNode{5, &node5, &node6}
	res := inorderTraversal(&node7)
	fmt.Printf("res: %v
", res) //res: [1 4 2 5 7 6 8]
}