Binary Tree Preorder Traversal

LeetCode #144

Description:

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

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

Example:

Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].

Idea:

Iteration version： 注意：

1. stack里要存TreeNode，每次pop出来，再把这个Node的左右子树push进stack
2. 先push进左子树，再push右边！

Code:

Iteration version

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> stack_node;

        if(root!=NULL)
            stack_node.push(root);

        while(!stack_node.empty()){
            TreeNode *node=stack_node.top();
            result.push_back(node->val);
            stack_node.pop();

            // Push right child first! Then push left child!
            if(node->right!=NULL) stack_node.push(node->right);
            if(node->left!=NULL) stack_node.push(node->left);
        }

        return result;
    }
};

Recursion version

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;

        RecursionPreorder(root, result);

        return result;
    }

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

        result.push_back(root->val);

        RecursionPreorder(root->left, result);
        RecursionPreorder(root->right, result);
    }
};