数据结构和算法基础篇二叉树的中序遍历

上一篇文章中，我们介绍了栈来实现二叉树的前序遍历。这一篇文章，我们还使用栈来实现二叉树的中序遍历。

所谓二叉树的中序遍历，就是先访问左子树，然后访问根节点，然后右子树。然后左子树的访问还是满足这个顺序。不熟悉遍历过程的朋友可以百度谷歌搜一下遍历的示例。

下面我们来看Leetcode上面的一道题目，怎么实现中序遍历。

94. Binary Tree Inorder Traversal

Given a binary tree, return theinordertraversal of its nodes' values.

Example:

Input:[1,null,2,3] 1 \ 2 / 3

Output:[1,3,2]

题目的要求给定了一个二叉树的根节点，然后要求输出中序遍历的结果。

二叉树的遍历采用递归版本的思路很简单，就是先递归左子树，然后根节点，最后右子树。参考代码如下：

递归遍历的核心代码其实就是三行：递归调用左子树，处理当前节点，递归右子树。递归的出口就是节点为空。

下面我们来看看非递归版本的思路。

非递归版本的思路就是，从根节点开始，一直找到最左边的节点。因为这个节点才是第一个节点。那么我们可以从根节点开始压入栈，如果当前节点存在左子树就继续压栈直到叶子节点。

当压入到了叶子节点了，就开始从栈中取一个节点。然后输出这个节点数据，接着处理这个节点的节点。