# leetcode 144 & 145

Binary Tree Preorder Traversal

preorder = 前序

postorder = 後序

記憶方式

前序 = root 在前 = root 左 右
中序 = root 在中 = 左 root 右
後序 = root 在後 = 左 右 root

## 144 pre order

// Time:  O(n)
// Space: O(h)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        preorderHelper(root);
        return result;
    }
private:
    vector<int> result;
    void preorderHelper(TreeNode* root) {
        if (root == nullptr)
            return ;
        result.push_back(root->val);
        preorderHelper(root->left);
        preorderHelper(root->right);
        return;
    }
};

## 145 post order

// Time:  O(n)
// Space: O(h)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        postorderHelper(root);
        return result;
    }
private:
    vector<int> result;
    void postorderHelper(TreeNode* root) {
        if (root == nullptr)
            return ;
        postorderHelper(root->left);
        postorderHelper(root->right);
        result.push_back(root->val);
        return;
    }
};