Epoch

Question

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

題意

  show 出 preorder，recursive 挺簡單的，iterative 也行嗎?

code

recursive

int *num;
int count=0;
int size=128;
void help_preorder(struct TreeNode* root){
    if(root!=NULL){
        /*
        if(count>size){
            size*=2;
            num = realloc(num, sizeof(int)*size);
        }
        */
        num[count] = root->val;
        count++;
        if(root->left)
            help_preorder(root->left);
        if(root->right)
            help_preorder(root->right);
    }
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int i;
    num = malloc(sizeof(int)*size);
    count=0;
    help_preorder(root);
    *returnSize = count;
    return num;
}

iterative using stack

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == NULL)
            return vector<int>();
        stack<TreeNode*> s;
        vector<int> num;
        s.push(root);
        while(!s.empty()){
            TreeNode* tmp = s.top();
            num.push_back(tmp->val);
            s.pop();
            if(tmp->right)
                s.push(tmp->right);
            if(tmp->left)
                s.push(tmp->left);
        }
        return num;
    }
};