• 144.二叉樹的前序遍歷(opens new window)
• 145.二叉樹的后序遍歷(opens new window)
• 94.二叉樹的中序遍歷

遞歸三部曲：
1.確定遞歸函數(shù)的參數(shù)和返回值： 確定哪些參數(shù)是遞歸的過程中需要處理的训裆，那么就在遞歸函數(shù)里加上這個(gè)參數(shù)置逻， 并且還要明確每次遞歸的返回值是什么進(jìn)而確定遞歸函數(shù)的返回類型舟奠。

2.確定終止條件： 寫完了遞歸算法, 運(yùn)行的時(shí)候蔚携，經(jīng)常會(huì)遇到棧溢出的錯(cuò)誤，就是沒寫終止條件或者終止條件寫的不對狼速，操作系統(tǒng)也是用一個(gè)棧的結(jié)構(gòu)來保存每一層遞歸的信息琅锻，如果遞歸沒有終止，操作系統(tǒng)的內(nèi)存棧必然就會(huì)溢出向胡。

3.確定單層遞歸的邏輯： 確定每一層遞歸需要處理的信息恼蓬。在這里也就會(huì)重復(fù)調(diào)用自己來實(shí)現(xiàn)遞歸的過程。

前序遍歷

#遞歸
class Solution {
public:
    void traversal(TreeNode* root, vector<int> &result) {
        if(root == nullptr) return;
        result.emplace_back(root->val);
        traversal(root->left, result);
        traversal(root->right, result);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

#迭代
class Solution {
public:
    void traversal(TreeNode* root, vector<int> &result) {
        if(root == nullptr) return;
        result.emplace_back(root->val);
        traversal(root->left, result);
        traversal(root->right, result);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

后序遍歷

#遞歸
 void traversal(TreeNode* root, vector<int>& result) {
        if(root == nullptr) return;
        traversal(root->left, result);
        traversal(root->right, result);
        result.emplace_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }

#迭代
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;

        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.emplace_back(node->val);
            if(node->left)st.push(node->left);
            if(node->right)st.push(node->right);
        }
        reverse(result.begin(), result.end());
        return result;
    }

中序遍歷

#遞歸
    void traversal(TreeNode* root, vector<int> &result) {
        if(root == nullptr) return;
        traversal(root->left, result);
        result.emplace_back(root->val);
        traversal(root->right, result);
    }
    

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }

#迭代
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;
        stack<TreeNode*> st;
        TreeNode *cur = root;
        while(!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();
                result.emplace_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }