Binary Tree Inorder Traversal-非递归实现中序遍历二叉树

题目描述：

给定一颗二叉树，使用非递归方法实现二叉树的中序遍历

题目来源：

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;
}