Binary Tree Inorder Traversal

Binary Tree Inorder Traversal

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

----------------------------------- thinking ---------------------------------------------------------
inorder traversal: In a loop, first adding all left nodes into the stack, then pop out all nodes that do not contain right child, then pop out the first node with the right child, then push in this node's left child
------------------------------------- codes ----------------------------------------------------------
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        if (root == NULL) {
            return result;
        }
        stack<TreeNode*> stack;
        stack.push(root);
        while (true) {
            TreeNode* node = stack.top();
            if (node->left) {
                stack.push(node->left);
                continue;
            }
           
            while (stack.size() && !stack.top()->right) {
                result.push_back(stack.top()->val);
                stack.pop();
            }
            if (stack.size() == 0) {
                return result;
            }
            node = stack.top();
            stack.pop();
            result.push_back(node->val);          
            stack.push(node->right);
        }
    }
};