二叉树的遍历（全面总结）
目录
二叉树遍历分为两大类：
二叉树节点结构
深度优先遍历（DFS）
二叉树前序递归遍历
二叉树前序非递归遍历
二叉树中序递归遍历
二叉树中序非递归遍历
二叉树后序递归遍历
二叉树后序非递归遍历
广度优先遍历（BFS）
二叉树的层序遍历
二叉树遍历分为两大类：
深度优先遍历（DFS）：前序、中序、后序
广度优先遍历（BFS）：层次遍历
掌握二叉树的遍历是理解和操作二叉树的基础。递归方法简洁易懂，迭代方法效率更高且避免栈溢出
二叉树节点结构
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) {} };深度优先遍历（DFS）
二叉树前序递归遍历
vector<int> preorderTraversal(TreeNode* root) { vector<int> result; preorder(root, result); return result; } void preorder(TreeNode* root, vector<int>& result) { if (!root) return; result.push_back(root->val); // 访问根 preorder(root->left, result); // 遍历左子树 preorder(root->right, result); // 遍历右子树 }二叉树前序非递归遍历
思路：前序非递归遍历需要借助栈
1. 如果树为空，直接返回
2. 如果树非空：从根节点位置开始遍历，因为前序遍历规则：根节点、左子树、右子树
a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈，并访问。
b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点，其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍历，继续a
代码实现：
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> st; TreeNode* cur = root; while(!st.empty() || cur) { // 每次循环表示要开始访问一颗树了，先将一颗数的左路节点都入栈并访问节点 // 剩余左路节点的右子树还没访问 while(cur) { v.push_back(cur->val); st.push(cur); cur = cur->left; } // 取栈中的节点依次访问左路节点的右子树 TreeNode* top = st.top(); st.pop(); cur = top->right; } return v; } };二叉树中序递归遍历
vector<int> inorderTraversal(TreeNode* root) { vector<int> result; inorder(root, result); return result; } void inorder(TreeNode* root, vector<int>& result) { if (!root) return; inorder(root->left, result); // 遍历左子树 result.push_back(root->val); // 访问根 inorder(root->right, result); // 遍历右子树 }二叉树中序非递归遍历
思路：中序非递归遍历需要借助栈 1. 空树，直接返回 2. 如果树非空：从根节点位置开始遍历，但此时根节点不能遍历，因为中序遍历规则：左子树、根节点、右子树 a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈 b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍历，继续a
代码实现：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { // 空树，直接返回 vector<int> vRet; if(nullptr == root) return vRet; TreeNode* pCur = root; stack<TreeNode*> s; while(pCur || !s.empty()) { // 找以pCur为根的二叉树最左侧的节点，并将所经路径中的节点入栈 while(pCur) { s.push(pCur); pCur = pCur->left; } pCur = s.top(); // pCur左子树为空，相当于左子树已经访问过了，可以直接访问以pCur为根的二叉树的根节点 vRet.push_back(pCur->val); s.pop(); // 以pCur为根的二叉树的左子树已经遍历完，根节点已经遍历， // 将pCur的右子树当成一棵二叉树来遍历 pCur = pCur->right; } return vRet; } };二叉树后序递归遍历
vector<int> postorderTraversal(TreeNode* root) { vector<int> result; postorder(root, result); return result; } void postorder(TreeNode* root, vector<int>& result) { if (!root) return; postorder(root->left, result); // 遍历左子树 postorder(root->right, result); // 遍历右子树 result.push_back(root->val); // 访问根 }二叉树后序非递归遍历
思路：后序非递归遍历需要借助栈 1. 空树，直接返回 2. 如果树非空：从根节点位置开始遍历，但此时根节点不能遍历，因为后序遍历规则：左子树、右子树、根节点 a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈 b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，但是此时该节点不能遍历，除非其右子树不存在或者其右子树已经遍历，才可以遍历该节点.如果该节点右子树没有遍历，将其右子树作为一棵新的二叉树遍历，继续a
代码实现：
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { // 空树直接返回 vector<int> vRet; if(nullptr == root) return vRet; TreeNode* pCur = root; TreeNode* pPrev = nullptr; stack<TreeNode*> s; while(pCur || !s.empty()) { // 找以pCur为根的二叉树最左侧的节点，并将所经路径中的节点入栈 while(pCur) { s.push(pCur); pCur = pCur->left; } TreeNode* pTop = s.top(); // pTop左子树已经访问 // 如果pTop的右子树是空，或者右子树已经访问过了，就可以访问pTop if(nullptr == pTop->right || pPrev == pTop->right) { vRet.push_back(pTop->val); s.pop(); // 将刚刚访问过的节点标记起来 pPrev = pTop; } else { // 如果右子树没有访问，将右子树当成一棵新的二叉树访问 pCur = pTop->right; } } return vRet; } };广度优先遍历（BFS）
二叉树的层序遍历
层序遍历：从上到下，从左到右逐层访问二叉树的所有节点。通过这个性质，我们可以联想到队列的FIFO特性（保证了节点按入队顺序访问），先入队的节点先访问，符合层序要求
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); vector<int> level; for (int i = 0; i < levelSize; i++) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(level); } return result; }