前中后序遍历（DFS）

首先我们要明确前中后序遍历的顺序：

• 前序：中左右
• 中序：左中右
• 后序：左右中

前中后序遍历的递归代码和迭代代码分别有各自的框架，然后根据遍历顺序调整记录元素的位置即可。

递归

class Solution {
private:
    void postOrder(TreeNode* root, vector<int>& vec) {
        if (!root) return;
        postOrder(root->left, vec);	// 1
        postOrder(root->right, vec);// 2
        vec.push_back(root->val);		// 3
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postOrder(root, res);
        return res;
    }
};

• 前序遍历：3->1->2
• 中序遍历：1->3->2
• 后序遍历：1->2->3

如前所述，三种遍历的迭代方式很简单，并且更改迭代方式只要调整记录元素的位置即可。

迭代

前序遍历

我们以前序遍历给出迭代版本的框架，核心思想就是用栈。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> S;
        TreeNode* node = root;
        while (node || !S.empty()) {
            while (node) {
                res.push_back(node->val);			// 注意
                S.push(node);
                node = node->left;
            }
            node = S.top();		
            S.pop();
            node = node->right;	
        }
        return res;
    }
};

中序遍历

与前序遍历的差别请看代码中的 注意，调整了记录元素的位置。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> S;
        TreeNode* curr = root;
        while (curr || !S.empty()) {
            while (curr) {
                S.push(curr);
                curr = curr->left;
            }
            TreeNode* node = S.top();
            S.pop();
            res.push_back(node->val);			// 注意
            curr = node->right;
        }
        return res;
    }
};

后序遍历

注意到前序遍历的顺序为：中左右，而我们想要的后序遍历的顺序为：左右中。我们可以先讲前序遍历代码中访问左右子树的顺序互换，得到顺序为：中右左，再进行 reverse，得到后序：左右中。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> S;
        S.push(root);
        while (!S.empty()) {
            TreeNode* node = S.top();
            S.pop();
            res.push_back(node->val);
            if (node->left) S.push(node->left);
            if (node->right) S.push(node->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

层序遍历（BFS）

不需按深度划分

直接输出层序遍历序列，不需按深度划分，不同于 DFS 使用栈，这里是用队。

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        if (!root) return {};
        queue<TreeNode*> Q;
        // vector<vector<int>> res;
        vector<int> res;
        Q.push(root);
        while (!Q.empty()) {
            TreeNode* curr = Q.front();
            res.push_back(curr->val);
            Q.pop();
            if(curr->left) Q.push(curr->left);
            if(curr->right) Q.push(curr->right);
        }
        return res;
    }
}

需要按深度划分

注意在不需要按深度划分的版本的基础上做些改变，用 n 记录当前深度的节点的个数，然后在 for 循环中将这 n 个节点保存到一个数组中，下一层深度再用一个新数组保存，从而达到按深度划分。

注意在本题的基础上修改，可解决 LeetCode 中许多层序遍历的变种问题。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        Q.push(root);
        while (!Q.empty()) {
            vector<int> vec;
            int n = Q.size();
            for (int i=0; i<n; ++i) {
                TreeNode* curr = Q.front();
                Q.pop();
                vec.push_back(curr->val);
                if (curr->left) Q.push(curr->left);
                if (curr->right) Q.push(curr->right);
            }
            res.push_back(vec);
        }
        return res;
    }
}

Ref：

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.md