二叉树的遍历
文章目录
二叉树的遍历 - 深度优先遍历（DFS）
- 二叉树的前序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
- 广度优先遍历（BFS）
- 层序遍历
二叉树是数据结构中的核心概念，遍历二叉树是理解其结构和操作的基础
深度优先遍历（DFS）
二叉树的前序遍历
顺序：根节点 → 左子树 → 右子树（简记为 “根左右”）
ABCDE二叉树的先序遍历序列为：ABDEC
- 递归实现
// 递归实现class Solution{public:vector<int>preorderTraversal(TreeNode*root){vector<int>result;preorderHelper(root,result);returnresult;}private:voidpreorderHelper(TreeNode*node,vector<int>&result){if(!node){return;}result.push_back(node->val);// 访问根节点preorderHelper(node->left,result);// 遍历左子树preorderHelper(node->right,result);// 遍历右子树}};- 迭代实现（使用栈）
// 迭代实现（使用栈）vector<int>preorderTraversalIterative(TreeNode*root){vector<int>result;if(!root){returnresult;}stack<TreeNode*>stk;stk.push(root);while(!stk.empty()){TreeNode*node=stk.top();stk.pop();result.push_back(node->val);// 右子节点先入栈，左子节点后入栈// 保证左子节点先被访问if(node->right){stk.push(node->right);}if(node->left){stk.push(node->left);}}returnresult;}- 迭代实现（另一种方式）
// 迭代实现（另一种方式）vector<int>preorderTraversalIterative2(TreeNode*root){vector<int>result;stack<TreeNode*>stk;TreeNode*curr=root;while(curr||!stk.empty()){// 遍历到最左侧节点while(curr){result.push_back(curr->val);// 访问当前节点stk.push(curr);curr=curr->left;}// 回溯并转向右子树curr=stk.top();stk.pop();curr=curr->right;}returnresult;}二叉树的中序遍历
顺序：左子树 → 根节点 → 右子树（简记为 “左根右”）
ABCDE二叉树的中序遍历序列为：DBEAC
- 递归
// 递归实现class Solution{public:vector<int>inorderTraversal(TreeNode*root){vector<int>result;inorderHelper(root,result);returnresult;}private:voidinorderHelper(TreeNode*node,vector<int>&result){if(!node)return;inorderHelper(node->left,result);// 遍历左子树result.push_back(node->val);// 访问根节点inorderHelper(node->right,result);// 遍历右子树}};- 迭代实现
// 迭代实现vector<int>inorderTraversalIterative(TreeNode*root){vector<int>result;stack<TreeNode*>stk;TreeNode*curr=root;while(curr||!stk.empty()){// 遍历到最左侧节点while(curr){stk.push(curr);curr=curr->left;}// 访问节点并转向右子树curr=stk.top();stk.pop();result.push_back(curr->val);curr=curr->right;}returnresult;}- 迭代实现
vector<int>inorderTraversalUnified(TreeNode*root){vector<int>result;stack<TreeNode*>stk;if(root)stk.push(root);while(!stk.empty()){TreeNode*node=stk.top();stk.pop();if(node){// 右中左的顺序入栈if(node->right)stk.push(node->right);// 右stk.push(node);// 中stk.push(nullptr);// 标记节点if(node->left)stk.push(node->left);// 左}else{// 遇到标记，访问节点node=stk.top();stk.pop();result.push_back(node->val);}}returnresult;}二叉树的后序遍历
顺序：左子树 → 右子树 → 根节点（简记为 “左右根”）
ABCDE二叉树的后序遍历序列为：DEBCA
- 递归
// 递归实现class Solution{public:vector<int>postorderTraversal(TreeNode*root){vector<int>result;postorderHelper(root,result);returnresult;}private:voidpostorderHelper(TreeNode*node,vector<int>&result){if(!node)return;postorderHelper(node->left,result);// 遍历左子树postorderHelper(node->right,result);// 遍历右子树result.push_back(node->val);// 访问根节点}};- 迭代实现（双栈法）
// 迭代实现（双栈法）vector<int>postorderTraversalTwoStacks(TreeNode*root){vector<int>result;if(!root)returnresult;stack<TreeNode*>stk1,stk2;stk1.push(root);while(!stk1.empty()){TreeNode*node=stk1.top();stk1.pop();stk2.push(node);if(node->left)stk1.push(node->left);if(node->right)stk1.push(node->right);}while(!stk2.empty()){result.push_back(stk2.top()->val);stk2.pop();}returnresult;}- 迭代实现
// 迭代实现vector<int>postorderTraversalUnified(TreeNode*root){vector<int>result;stack<TreeNode*>stk;if(root)stk.push(root);while(!stk.empty()){TreeNode*node=stk.top();stk.pop();if(node){// 中右左的顺序入栈stk.push(node);// 中stk.push(nullptr);// 标记节点if(node->right)stk.push(node->right);// 右if(node->left)stk.push(node->left);// 左}else{// 遇到标记，访问节点node=stk.top();stk.pop();result.push_back(node->val);}}returnresult;}广度优先遍历（BFS）
层序遍历
顺序：从上到下，从左到右逐层遍历
// 基本层序遍历（返回一维数组）vector<int>levelOrder(TreeNode*root){vector<int>result;if(!root)returnresult;queue<TreeNode*>q;q.push(root);while(!q.empty()){TreeNode*node=q.front();q.pop();result.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}returnresult;}