94_144_145 Preorder_Inorder_Postorder (Recursive & Iteratively)

#easy

Recursive => memory較低，運行時間較長
Iterative => memory較高，運行時間較短

Preorder (中左右)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    void pre_recursive( vector<int> & v_res, TreeNode * root ) {
        if ( root == NULL ) return;
        v_res.push_back( root -> val );
        pre_recursive( v_res, root -> left );
        pre_recursive( v_res, root -> right );
    }

    vector<int> preorderTraversal(TreeNode * root) {
        vector<int> v_res;
        // Method 1. recursive
        // pre_recursive( v_res, root );

        // Method 2. iterative
        stack<TreeNode*> st;
        if ( root == NULL ) return {};
        st.push(root);
        while ( !st.empty() ) {
            TreeNode * node = st.top();
            st.pop();
            v_res.push_back( node->val ); 
            if ( node -> right != NULL ) st.push(node->right);
            if ( node -> left != NULL ) st.push(node->left);
        }
        return v_res;
    }
};

Inorder (左中右)

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

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v_res;
        // Method 1 recursive
        // ino_recursive( v_res, root );
        // return v_res;

        // Method 2 interative
        stack<TreeNode*> st;
        if ( root == NULL ) return {};
        TreeNode* cur = root;
        while ( !st.empty() || cur != NULL ) {
            if (cur != NULL) { // 指針來訪問節點，訪問到最底層
                st.push(cur); // 將訪問的節點放進棧
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 從棧裡彈出的數據，就是要處理的數據（放進result數組裡的數據）
                st.pop();
                v_res.push_back(cur->val); // 左,中
                cur = cur->right;          // 右
            }
            
        }

        return v_res;
    }
};

Postorder (左右中)

reverse( inorder )

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



    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v_res;
        // post_recursive( v_res, root );
        // return v_res;
        stack<TreeNode*> st;
        if ( root == NULL ) return {};
        st.push(root);
        while ( !st.empty() ) {
            TreeNode * node = st.top();
            st.pop();
            v_res.push_back( node -> val );
            if ( node -> left != NULL ) st.push( node -> left );
            if ( node -> right != NULL ) st.push( node -> right ); 
        }

        reverse( v_res.begin(), v_res.end() );
        return v_res;
    }
};