题目描述：
给定一颗二叉树，使用非递归方法实现二叉树的中序遍历
- 题目来源：
- http://oj.leetcode.com/problems/binary-tree-inorder-traversal/
- 题目分析：
- 递归到非递归的转换。使用栈描述递归的调用过程， while循环体计算递归程序的计算部分 。因为每次while循环只能处理一次递归调用， 使用标记记录栈中节点的计算痕迹 ，例如：用tag记录当前根的调用记录，当根的左右子树均未调用时，令tag值为0，当根的左子树已经调用过时，令tag值为1。
- 时间复杂度： O（n） n为节点数
- 示例代码：
vector<
int
> inorderTraversal(TreeNode *
root) {
stack
<TreeNode*>
stnode;
stack
<
char
>
sttag;
vector
<
int
>
result;
if
(root ==
NULL)
return
result;
stnode.push(root);
sttag.push(
'
0
'
);
while
(!
stnode.empty()) {
TreeNode
* topnode =
stnode.top();
char
toptag =
sttag.top();
if
(toptag ==
'
0
'
) {
sttag.pop();
sttag.push(
'
1
'
);
if
(topnode->left !=
NULL) {
stnode.push(topnode
->
left);
sttag.push(
'
0
'
);
}
}
else
if
(toptag ==
'
1
'
) {
result.push_back(topnode
->
val);
stnode.pop();
sttag.pop();
if
(topnode->right !=
NULL) {
stnode.push(topnode
->
right);
sttag.push(
'
0
'
);
}
}
}
return
result;
}
