144. Binary Tree Preorder Traversal

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

Example:

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

Output: [1,2,3]

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

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

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

94. Binary Tree Inorder Traversal145. Binary Tree Postorder Traversal