写在前面

之前介绍过面试题：二叉树的非递归前序遍历、面试题：二叉树的非递归中序遍历、面试题：二叉树的非递归后序遍历，感兴趣的同学可以先去看看那几篇文章。

前序和中序的非递归算法非常相似，包括后序的方法三介绍的算法也很相似。本文将总结这3个相似算法的相同点，总结出一套万能模板，适用于二叉树的前序、中序、后序非递归算法。

万能模板

1.定义一个栈和cur指针
2.将cur及其所有左子孙节点入栈
3.出栈
4.将cur指向它的右孩子，然后从步骤2开始循环

模板代码

// 定义节点
type Node struct {
	Val         int
	Left, Right *Node
}

func TreeVisit(root *Node) []int {
	result := []int{}
	// 1.定义一个栈
	s := newStack()
	cur := root
	for true {
		// 从当前点开始，将它及其所有的左子孙都入栈
		for cur != nil {
			// TODO: 如果是前序遍历，则在此处访问cur节点。因为前序遍历的顺序是：中、左、右，因此需要先访问，然后入栈
			// cur入栈
			s.push(cur)
			cur = cur.Left
		}
		// 如果栈为空，则退出循环
		if s.empty() {
			break
		}
		// 此时当前节点cur为空，弹出栈顶元素
		cur = s.pop()
		// TODO: 如果是中序遍历，则在此处访问cur节点。因为中序遍历的顺序是：左、中、右，此时以cur为根节点的子树，左孩子为空或者已经被访问过了，此时应该访问cur节点了
		// TODO: 如果是后序遍历，则在此处访问cur节点。因为后序遍历的顺序是左、右、中，此时以cur为根节点的子树，左孩子为空或者已经被访问过了。但是能不能访问cur节点
		// 还不确定，还需要判断一下它的右孩子是否已经被访问过，因此需要增加一个pre节点记录上一次访问过的节点，如果pre=cur.Right则表示cur的右孩子已经被访问过，可以访问cur了。
		// 可以确定的是，在后序遍历中，访问完右孩子，紧接着肯定是访问根节点，所以pre一定是等于cur的右孩子，如果不是说明cur的右孩子还没被访问。
		// 指向当前节点的右孩子
		cur = cur.Right
	}

	return result
}

上面模板代码中，在关键地方列出了TODO，下面利用万能模板分别实现前序、中序、后序算法

前序

// 二叉树的非递归前序遍历
func TreeBeforeVisit(root *Node) []int {
	result := []int{}
	// 1.定义一个栈
	s := newStack()
	cur := root
	for true {
		// 从当前点开始，将它及其所有的左子孙都入栈
		for cur != nil {
			// 在此处访问cur节点
			result = append(result, cur.Val)
			// cur入栈
			s.push(cur)
			cur = cur.Left
		}
		// 如果栈为空，则退出循环
		if s.empty() {
			break
		}
		// 此时当前节点cur为空，弹出栈顶元素
		cur = s.pop()
		cur = cur.Right
	}

	return result
}

中序

// 二叉树的非递归中序遍历
func TreeMidVisit(root *Node) []int {
	result := []int{}
	// 1.定义一个栈
	s := newStack()
	cur := root
	for true {
		// 从当前点开始，将它及其所有的左子孙都入栈
		for cur != nil {
			// cur入栈
			s.push(cur)
			cur = cur.Left
		}
		// 如果栈为空，则退出循环
		if s.empty() {
			break
		}
		// 此时当前节点cur为空，弹出栈顶元素
		cur = s.pop()
		result = append(result, cur.Val)
		cur = cur.Right
	}

	return result
}

后序

// 二叉树的非递归中序遍历
func TreeAfterVisit(root *Node) []int {
	result := []int{}
	// 1.定义一个栈
	s := newStack()
	cur := root
	var pre *Node
	for true {
		// 从当前点开始，将它及其所有的左子孙都入栈
		for cur != nil {
			// cur入栈
			s.push(cur)
			cur = cur.Left
		}
		// 如果栈为空，则退出循环
		if s.empty() {
			break
		}
		// 此时当前节点cur为空，弹出栈顶元素
		cur = s.pop()
        // 只有当cur的右孩子为空或者cur的右孩子已经访问过了，才能访问cur，所以需要用pre记录上一次访问到的节点
		if cur.Right == nil || cur.Right == pre {
			// 访问cur节点
			result = append(result, cur.Val)
			pre = cur
			cur = nil // 这步很重要。逻辑走到这里说明以p为根的子树已经访问完了，下一步需要访问p的父节点，需要从栈栈弹出一个元素，所以这里将p设置为空
		} else {
            // 否则访问p的右孩子
			s.push(cur) // 这一步很重要，需要将p重新放回栈，p不能被丢弃，后面还要访问p
			cur = cur.Right
		}
	}

	return result
}

后序的算法要复杂一点，需要用pre指针记录一下上一次访问到的节点，并且如果不能访问cur节点，还需要放回栈。