1 题目
二叉树的中序遍历（Binary Tree Preorder Traversal）
lintcode：题号——67，难度——easy
2 描述
给出一棵二叉树，返回其节点值的中序遍历。
名词：
遍历
按照一定的顺序对树中所有节点进行访问的过程叫做树的遍历。
中序遍历
在二叉树中，首先遍历左子树，然后访问根结点，最后遍历右子树，在遍历左右子树时，仍然采用这种规则，这样的遍历方式叫做二叉树的中序遍历。
序列化规则：
使用大括号包裹节点序列来表示二叉树，首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点，之后以此类推。
样例1：
输入：二叉树 = {1,2,3}
输出：[2,1,3]
解释：上述{1,2,3}序列按照序列化规则表示的二叉树如下1 / \ 2 3按照前序遍历规则，先根再左右子树，顺序即为[2,1,3]
样例2：
输入：二叉树 = {1,#,2,3}
输出：[1,3,2]
解释：上述{1,#,2,3}序列按照序列化规则表示的二叉树如下1 / \ # 2 / 3按照前序遍历规则，先根再左右子树，顺序同样为[1,3,2]
3 解决方案
中序遍历与前序遍历[1]一样可以使用递归和非递归两类方式，递归和非递归各自的优缺点在前序遍历中也提到了。
3.1 递归算法
递归写法比较简单，主要注意防止死循环，递归的过程中要明确递归的三要素。
递归的三要素：
- 递归的定义（递归函数的返回值、参数要如何定义）
- 递归的拆解（递归如何向下拆分）
- 递归的出口（递归的结束条件）
递归又有两种形式，遍历和分治。
3.1.1 遍历法（Traverse）
思路
遍历的整个过程可以看成是为了完成某项大任务，于是领导亲自下基层处理各项小任务，所有工作都“亲历亲为”，参与了所有工作最终完成了大任务。
遍历法的主要递归函数一般不带返回值，会拥有
全局参数或者贯穿整个递归过程的函数参数用来处理数据。
源码
C++版本：
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
vector<int> inorderTraversal(TreeNode * root) {
// write your code here
vector<int> result;
traverse(root, result);
return result;
}
// 遍历法的递归函数，没有返回值，函数参数result贯穿整个递归过程用来记录遍历的结果
void traverse(TreeNode * cur, vector<int> & result) // 递归三要素之定义
{
if (cur == nullptr)
{
return; // 递归三要素之出口
}
// 此处与前序遍历不同，先处理左子树，再处理根节点，最后处理右子树
traverse(cur->left, result); // 递归三要素之拆解
result.push_back(cur->val);
traverse(cur->right, result);
}
3.1.2 分治法（Devide And Conquer）
思路
分治法的整个过程可以看成是为了完成某项大人物，于是领导把各项工作分派给各个下属，各个下属又把工作继续细分层层向下分派给基层人员，每一级都只需要获取下级完成的任务结果即可，最终所有层级任务都完成了，大任务也对应完成了。
分治法的主要递归函数一般需要有返回值，用来向上一层提供结果。
源码
C++版本：
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
// 由于主函数的形式已经符合分治法需要的形式（具有合适的返回值），直接使用主函数做为递归函数
vector<int> inorderTraversal(TreeNode * root) {
// write your code here
vector<int> result;
if (root == nullptr)
{
return result; // 递归三要素之出口
}
// 获取左子树的遍历结果
vector<int> leftResult = inorderTraversal(root->left); // 递归三要素之拆解
// 获取右子树的遍历结果
vector<int> rightResult = inorderTraversal(root->right);
// 此处与前序遍历不同，先处理左子树，再处理根节点，最后处理右子树
result.insert(result.end(), leftResult.begin(), leftResult.end());
result.push_back(root->val);
result.insert(result.end(), rightResult.begin(), rightResult.end());
return result;
}
3.2 非递归算法
3.2.1 二叉树遍历的非递归通用解法
思路
在中序遍历的非递归算法中，与前序遍历[1:1]唯一的不同之处在于对节点的解析操作发生的时刻，前序遍历是“边入栈边解析”，而中序遍历是“出栈时解析”。
- 左穿入栈到底；
- 从栈内弹出当前节点，可能是
左子树或者根节点（相对），出栈时解析； -
右子树的根节点入栈，重复1、2步骤（即对右子树做中序遍历），直到满足循环结束条件，该二叉树的中序遍历即在结果序列中。
中序遍历的初始条件和循环结束条件在通用解法中与前序遍历一致。
初始条件：栈为空、当前指针指向根节点。
循环结束条件：栈为空且当前指针为空。
源码
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
vector<int> inorderTraversal(TreeNode * root) {
// write your code here
vector<int> result;
if (root == nullptr)
{
return result;
}
stack<TreeNode *> nodeStack;
TreeNode * cur = root;
while (!nodeStack.empty() || cur != nullptr)
{
while (cur != nullptr)
{
nodeStack.push(cur);
cur = cur->left;
}
cur = nodeStack.top();
result.push_back(cur->val); // 此处是通用解法中唯一与前序遍历不同的地方，出栈时解析
nodeStack.pop();
cur = cur->right;
}
}
图解
在解法中，中序遍历的过程与前序遍历[1:2]基本一致，可以参考前序遍历的图解，区别只是解析操作发生的时刻不同。
3.3 时间复杂度
对二叉树的遍历，不管使用什么方式都是将整棵树中的所有节点走一遍，所以算法的时间复杂度都为O(n)。
关于二叉树和分治法的时间复杂度的更多内容，在前序遍历[1:3]中已经进行了计算分析。
3.4 空间复杂度
算法的空间复杂度，分治法为O(n)，上述其余方法都为O(1)。