Binary Tree Inorder Traversal

LeetCode #94

Description:

Given a binary tree, return the inorder traversal of its nodes' values. Note: Recursive solution is trivial, could you do it iteratively?

Example:

Given binary tree [1,null,2,3],
   1
    \
     2
    /
   3
return [1,3,2].

Idea:

如果not null，先把left全push进stack 如果是null，pop stack，visit， 然后p=p->right 回到loop

Code:

Iteration version

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> result;
        stack<TreeNode *> stack_node;
        TreeNode *p=root;

        while(!stack_node.empty()||p!=NULL){
            if(p!=NULL){
                stack_node.push(p);
                p=p->left;
            }
            else{
                p=stack_node.top();
                stack_node.pop();
                result.push_back(p->val);
                p=p->right;
            }
        }
        return result;
    }
};

Recursion version

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> result;

        RecursionInorder(root, result);

        return result;
    }

    void RecursionInorder(TreeNode* root, vector<int> &result){
        if(root==NULL) return;

        RecursionInorder(root->left, result);

        result.push_back(root->val);

        RecursionInorder(root->right, result);
    }
};