二叉树的三种递归遍历

文档和视频讲解：代码随想录(programmercarl.com)

状态：ac

用时：0.5h

思路：递归的三个要素，即

图1 递归三要素

第一点，二叉树遍历除了打印节点数值，不需要其他处理，无需返回值。第二点终止条件即当前遍历节点为空。第三点，注意是先遍历左右节点还是打印中间节点，三者之间的顺序是不同遍历方式递归的处理逻辑。

代码：

图2 前、中、后序递归遍历

三种迭代遍历

文档和视频讲解：代码随想录(programmercarl.com)

状态：ac

用时：1.5h

思路和代码：

前序遍历：顺序为中左右，用一个栈存放节点指针，在处理完栈顶的节点指针后，放入该节点的左右节点，注意按照先右后左的顺序，因为栈后入先出，所以后放入左，则先处理左子节点。

中序遍历：顺序为左中右，由于遍历访问和处理的顺序不像前序遍历一样同步，因此指针遍历数，而用栈来处理节点。

后序遍历：顺序为左右中，其实可以通过更改前序遍历的处理顺序和结果数组顺序来更改实现。

图3 后序遍历

图4 前序遍历迭代

图5 中序遍历迭代

图6 后序遍历迭代