LeetCode: Binary Tree Preorder Traversal

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

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

   1
    \
     2
    /
   3

return [1,2,3].

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

---

We can use a stack to simulate the recursive call.

C++ Code:

/*
 * func: preorder_traversal
 * goal: give the preorder traversal of the tree
 * @param root: root node
 * return: preorder traversal list
 */
vector<int> preorder_traversal(TreeNode *root){
    vector<int> result;
    if(root == nullptr){
        return result;
    }
    stack<TreeNode *> preorder_helper;
    preorder_helper.emplace(root);
    while(!preorder_helper.empty()){
        TreeNode *curr = preorder_helper.top();
        result.emplace_back(curr->val);
        preorder_helper.pop();
        if(curr->right)
            preorder_helper.emplace(curr->right);
        if(curr->left)
            preorder_helper.emplace(curr->left);
    }
    return result;
}

Python Code:

# func: preorder traversal of the tree
# @param root: root node
# @return: traversal list
def preorder_traversal(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        curr = stack[-1]
        stack = stack[:-1]
        result.append(curr.val)
        if curr.right:
            stack.append(curr.right)
        if curr.left:
            stack.append(curr.left)
    return result