golang 非递归遍历二叉树

1 先序遍历

func PreOrder(t *TreeNode) []int{
	var res []int
	if t == nil {
		return res
	}
	stack := list.New()
	for t != nil || stack.Len() > 0{
		//1 遍历当前节点，如果当前阶段左孩子不为空，则遍历左孩子节点，直到找到左孩子为空的节点
		for t != nil {
			res = append(res, t.Val)
			stack.PushBack(t)
			t = t.Left
		}
		//2 pop 当前已遍历节点，使用步骤1 遍历当前已遍历节点的右孩子
		if stack.Len() > 0 {
			cur := stack.Back()
			t = cur.Value.(*TreeNode).Right
			stack.Remove(cur)
		}
	}
	return res
}

2 中序遍历

func MidOrder(t * TreeNode) (res []int) {
	stack := list.New()
	for t != nil || stack.Len() > 0 {
		//1 压栈当前节点，如果当前节点左孩子不为空，压栈当前节点左孩子节点，直到找到左孩子为空的节点
		for t != nil {
			stack.PushBack(t)
			t = t.Left
		}
		//2 遍历栈顶节点，pop栈顶节点，如果当前节点右孩子不为空，则遍历节点右孩子
		if stack.Len() > 0 {
			e := stack.Back()
			stack.Remove(e)
			t = e.Value.(*TreeNode)
			res = append(res, t.Val)
			t = t.Right
		}
	}

	return
}

3 后续遍历

func PostOrder(t *TreeNode) (res []int) {
	stack := list.New()
	var LastVisited *TreeNode
	for t != nil || stack.Len() > 0 {
		// 1 顺着左边一直压栈
		for t != nil {
			stack.PushBack(t)
			t = t.Left
		}
		e := stack.Back()
		top := e.Value.(*TreeNode)
		// 2 分析栈顶元素，是否应该遍历他，如果需要遍历，则更新最后遍历节点，pop此元素
		if top.Right == nil && top.Left == nil ||
			LastVisited == top.Right ||
			LastVisited == top.Left && top.Right == nil{
			res = append(res, top.Val)
			LastVisited = top
			stack.Remove(e)
		} else {
			// 如果不能遍历，则使用1 2 逻辑处理栈顶元素的右孩子
			t = top.Right
		}
	}
	return
}

func PostOrderReverse(t *TreeNode) (res []int) {
	stack := list.New()
	for t != nil || stack.Len() > 0 {
		// 1 顺着右边一直遍历，压栈，
		for t != nil {
			res = append(res, t.Val)
			stack.PushBack(t)
			t = t.Right
		}
		// 2 pop栈顶节点，压栈栈顶节点的左孩子
		if stack.Len() > 0 {
			e := stack.Back()
			stack.Remove(e)
			t = e.Value.(*TreeNode).Left
		}
	}
	length := len(res)
	// 得到的顺序为 中右左，需要把顺组翻转，称为 左右中
	for i := 0; i <= length/2;i ++ {
		res[i],res[length -1 - i] = res[length -1 - i], res[i]
	}
	return
}