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?

// Recursion
void helper(TreeNode* root, vector<int>& res) {
    if (!root) return;
    helper(root->left, res);
    res.push_back(root->val);
    helper(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) { // time: O(n); space: O(n)
    vector<int> res;
    helper(root, res);
    return res;
}

// Iteration
vector<int> inorderTraversal(TreeNode* root) { // time: O(n); space: O(n)
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

144. Binary Tree Preorder Traversal

145. Binary Tree Postorder Traversal