二叉树常见的遍历方式有三种（除去Level Traversal，也就是广度优先遍历），分别为先序遍历，中序遍历和后序遍历，而实现方式既有递归的实现方式也有非递归的实现方式。当然，递归的实现方式是最简单的。



遍历方式

二叉树的三种遍历方式为：



• 先序遍历：根->左->右

• 中序遍历：左->根->右

• 后序遍历：左->右->



对于以上这样一个简单的二叉树，如果我们以不同的遍历方式输出节点的值，那么产生的值的顺序为：

• 先序遍历：10 5 1 6 19 17 21

• 中序遍历：1 5 6 10 17 19 21

• 后序遍历：1 6 5 17 21 19 10

递归

我们先来看一下一个标准的递归访问树节点的实现方式

func traverse(root TreeNode) {
	if root ==  nil {
		return 
	}
	traverse(root.Left, arr)
	traverse(root.Right, arr)
}
func treeTraversal(root TreeNode) []int {
	return traverse(root)
}



这是一个很标准简洁的递归访问树节点的方式，具体的访问顺序如下图

这里仅仅画出了从root到左子树的访问和返回顺序，右子树大致相同。箭头上黑色的数字代表进入下一层递归，比如当root代表值为10的节点时候，图中箭头上1代表

   traverse(root.Left, arr)

而箭头上红色的数字代表该层函数结束，返回上一层，比如当root代表值为1的节点的时候，图中箭头上的红色4代表

   if root ==  nil {
        return 
    }

返回到上一层调用者的步骤。

我们通过观察可以发现，我们的递归函数以固定的顺序访问树中的每一个节点，但是三种不同的遍历方式要求处理/输出的节点的顺序却是不一样，那么如何能用这个统一的递归访问方式来得到不同顺序的处理结果呢？关键点就在处理函数（对节点进行处理的函数，最简单的就是将节点值输出到标准输出流println）的放置位置。

统一的实现

先序遍历：根->左->右

由于先序遍历是根->左->右，那么我们应该把函数放在访问左右节点之前，也就是

   handle(root.Value)
   traverse(root.Left, arr)
   traverse(root.Right, arr) 



中序遍历：左->根->右

由于中序遍历是左->根->右，那么我们应该把函数放在访问左节点之前和右节点之前，也就是

   traverse(root.Left, arr)
   handle(root.Value)
   traverse(root.Right, arr) 



后序遍历：左->右->根

由于后序遍历是左->右->根，那么我们应该把函数放在访问左节点和右节点之后，也就是

   traverse(root.Left, arr)
   traverse(root.Right, arr) 
   handle(root.Value)

总结

虽然二叉树的遍历方式有三种，但是实现起来其实代码是几乎一摸一样的， 我们以固定的顺序去拜访这些节点，区别只是处理节点的函数摆放的位置不同，先序是还未拜访左右子节点之前就调用处理函数，中序是拜访完左子节点就调用，后序是拜访完左右子节点再调用处理函数。