二叉树的遍历

二叉树的遍历

深度优先遍历（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;}