94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

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

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

此题考的是中序遍历的非递归实现，平时不注意积累导致不会写，从现在开始要注意。

非递归实现最关键的点在于，如何保留从根节点遍历下来的信息呢？

如果联想到递归实现的过程，就很容易想到使用栈来保存，因为子程序的调用中参数就是被压入栈中的。

如何知道自己已经掌握了这种方法呢？可以举一个简单的例子，通过写出栈Seq中的元素变化来确定。

以下图为例:)

Seq栈中的元素变化是：

[A]->[A,B]->[A,B,D]->[A,B]->[A,B,G]->[A,B]->[A]->[A,E]->[A]->[]->[C]->[]->[F]->[]

class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
if (root == NULL)
return result;
pCur = root;
while (!Seq.empty() || pCur)
{
if (pCur)
{
Seq.push(pCur);
pCur = pCur->left;
}
else
{
TreeNode *ptr = Seq.top();
result.push_back(ptr->val);
Seq.pop();
pCur = ptr->right;
}
}
        return result;
}
TreeNode* pCur;
vector<int> result;
stack<TreeNode*> Seq;
};