题目要求
给定一个二叉树，返回中序遍历的结果。
注：尝试用递归和迭代两种方法。
相似题目
解答： leetcode 144. Binary Tree Preorder Traversal(二叉树的前序遍历，递归法，非递归法)
示例
/* Example */
Input: [1,null,2,3]1\2/3Output: [1,3,2]
解题思路
什么是中序遍历？
中：指的是根节点出现的位置，以一个简单的树型结构举例，对树中的每个节点，在遍历的时候都按照先遍历左孩子，中间遍历根节点，最后遍历右孩子。
(结果为: 3-2-1)。
2/ \3 1
以此类推，我们可以知道先序遍历是先遍历根节点，然后是左孩子，最后是右孩子。（结果为：2-3-1）
后序遍历是：先遍历左孩子，中间是右孩子，最后是根节点。（结果为：3-1-2）
怎么实现中序遍历？
1、递归
递归方法是解决树类问题中常用的方法，易于理解，在解答本题的时候，我们根据上面讲的中序遍历方法，能写出如下的代码：
/*vector <int> inorder; // 保存节点的值。 */
vector<int> inorderTraversal(TreeNode* root) {
inorderTraversal(root->left); // 先递归遍历左节点到头inorder.push_back(root->val); // 输出inorderTraversal(root->right); // 后递归遍历右节点到头}
递归主要代码（c++）
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {
if(root !=NULL){
inorderTraversal(root->left);inorder.push_back(root->val);inorderTraversal(root->right);}return inorder;}private:vector<int> inorder;}
2、 迭代法（非递归）
由于递归实现树的遍历非常简单，所以在面试的时候，面试官通常会不让我们用递归来做，所以这里我们介绍一下非递归实现树的遍历。需要借助 栈 这个数据结构来实现。
我们来想一下，中序遍历的要点是根节点出现在中间的位置（先左中根后右）。
我们如何利用栈的特性（先进后出）来实现这个关系呢？
step1. 对一个二叉树(如下图)，我们首先要做的是从根开始遍历其左孩子，直到叶子节点4（再无左孩子为止）。
期间遍历到的所有节点都要进栈。
现在栈内有2，3，4。栈顶元素是4。
2/ \ | |3 1 | 4 | --->stack.top()/ / \ | 3 |
*4 5 6 | 2 |————————tree stack
step2. 对于4这个节点进行排序，根据中序遍历的顺序，先左孩子节点，但是此时没有左孩子结点，所以我们要返回根节点的值，即4。这时候你会发现，现在存于栈顶的元素，就是我们要找的，所以借助出栈操作来实现元素出栈，并且保存下根节点的值。（由于要取栈的栈顶元素操作，所以这个循环的条件之一就是保持栈非空！！可以看代码理解）
step3. 根据遍历的顺序，最后该遍历右孩子结点，我们只需要将现在的指针指向右侧孩子结点即可。
时间复杂度O(n),每个节点都遍历一次， 空间复杂度O(n)要存一个树形结构。
非递归主要代码–AC 0ms（c++）
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
vector<int> inorderTraversal(TreeNode* root) {
TreeNode*p = root;stack<TreeNode*>s;vector<int>nodes;while(!s.empty()||p) // 这步判断很重要，不要忘记栈非空。{
if(p){
s.push(p);p=p->left;}else{
p = s.top();s.pop();nodes.push_back(p->val);p=p->right;}} return nodes;}
总结一下
在实现非递归排序的时候，我们利用栈的特性，帮助我们十分高效的完成任务，需要注意的点有：
-
循环条件的设置，保证当前节点和栈的非空性十分重要，否则很大可能会Runtime error.
-
牢记栈的操作，push 进， pop 出（先要指向top()）