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].
``````

# 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);
}
};
``````