写在前面

前面分别介绍了面试题：二叉树的非递归前序遍历和面试题：二叉树的非递归中序遍历，举一反三，本文介绍二叉树的非递归后序遍历

方法一

作者觉得这是最简单的一种方法，就是用两个栈。

申请两个栈s1, s2。后序遍历的步骤如下：

申请一个栈记为s1, 然后初始将根节点进行入栈s1
从s1中弹出结点记做为cur, 然后将cur的不为空的左右孩子进行入栈s1。将弹出的cur进行入栈s2。
不断重复上面的步骤1和步骤2，直到s1为空
从s2中弹出元素并打印，打印序列就是后序遍历的顺序。

第二步依次将左右孩子入栈，后面出栈的顺序是右左，所以栈s2中的顺序是中右左，最后出栈就将顺序反过来了，结果是左右中。就是后序遍历了。

下面看具体代码

func TreeAfterVisit(root *Node) []int {
	if root == nil {
		return nil
	}
	// 1.定义一个栈
	s := newStack()
	// 2.定义一个栈
	s1 := newStack()
	// 根节点进栈
	s.push(root)
	//var pre *Node
	for true {
		// 第一个节点出栈
		if s.empty() {
			break
		}
		p := s.pop()
		// p进入s1
		s1.push(p)

		// 将栈顶元素的左右孩子入栈
		if p.Left != nil {
			s.push(p.Left)
		}
		if p.Right != nil {
			s.push(p.Right)
		}
	}

	result := []int{}
	for !s1.empty() {
		result = append(result, s1.pop().Val)
	}
	return result
}

方法二

后序遍历是左右中，而前序遍历是中左右，能不能将前序遍历的顺序改一下，改成中右左，然后再逆序，结果就是左右中？

方法二就是这个思路，主要代码如下

func TreeAfterVisit2(root *Node) []int {
	result := []int{}
	// 1.定义一个栈
	s := newStack()
	p := root
	for true {
		for p != nil {
			// 访问栈顶元素
			result = append(result, p.Val)
			// p入栈
			s.push(p)
			p = p.Right // 注意这里指向右孩子，所有右孩子入栈
		}
		// 从栈顶出战
		if s.empty() {
			break
		}
		p = s.pop()

		// 指向左孩子
		p = p.Left
	}

	return reverse(result)
}

func reverse(data []int) []int {
	n := len(data)
	for i := 0; i < n/2; i++ {
		data[i], data[n-1-i] = data[n-1-i], data[i]
	}
	return data
}

方法二使用的是一个栈，其实方法一夜可以使用一个栈，栈s2的左右就是为了做个逆序操作。

方法三

方法三有点难以理解，先上代码，后面再分析逻辑

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

	return result
}

这个算法的巧妙之处在于，记录了一下上一次访问过的节点pre，当要访问当前节点的时候，只有当前节点的右孩子为空，或者右孩子已经被访问过，才能访问当前节点。