

二叉树的遍历
Fri Feb 21 2025
Guide
二叉树的遍历
二叉树的定义
//二叉树
class TreeNode{
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode():val(0),left(nullptr),right(nullptr){}
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
广度优先搜素
借助使用队列(queue)来存储遍历的节点,按照二叉树的每一层从前到后的顺序进行遍历
vector<vector<int>> traversal(TreeNode* root){
vector<vector<int>> res;
if (root== nullptr){
return res;
}
queue<TreeNode*> que;
que.push(root);
while (!que.empty()){
int size=que.size();
vector<int> temp;
for (int i = 0; i < size; ++i) {
TreeNode* tempNode=que.front();
que.pop();
temp.push_back(tempNode->val);
if (tempNode->left){
que.push(tempNode->left);
}
if (tempNode->right){
que.push(tempNode->right);
}
}
}
return res;
}
深度优先搜索
递归法:
vector<int> res;
//前序遍历:中左右
void preTraversal(TreeNode* cur){
if (cur== nullptr){
return;
}
res.push_back(cur->val);
traversal(cur->left);
traversal(cur->right);
}
//中序遍历:左中右
void midTraversal(TreeNode* cur){
if (cur== nullptr){
return;
}
traversal(cur->left);
res.push_back(cur->val);
traversal(cur->right);
}
//后序遍历:左右中
void postTraversal(TreeNode* cur){
if (cur== nullptr){
return;
}
traversal(cur->left);
traversal(cur->right);
res.push_back(cur->val);
}
迭代法:
vector<int> res;
//前序遍历:中左右
void traversal(TreeNode* cur){
if (cur== nullptr){
return;
}
stack<TreeNode*> st;
st.push(cur);
while (!st.empty()){
TreeNode* temp=st.top();
st.pop();
res.push_back(temp->val);
if (temp->right){
st.push(temp->right);
}
if (temp->left){
st.push(temp->left);
}
}
}
//后序遍历:左右中
void postTraversal(TreeNode* cur){
if (cur== nullptr){
return;
}
stack<TreeNode*> st;
st.push(cur);
while (!st.empty()){
TreeNode* temp=st.top();
st.pop();
res.push_back(temp->val);
if (temp->left){
st.push(temp->left);
}
if (temp->right){
st.push(temp->right);
}
}
//注意:上面的顺序时中游右左,经过下面的调整变成了左右中
reverse(res.begin(),res.end());
}
//中序遍历:左中右
void midTraversal(TreeNode* root){
if (root==nullptr){
return;
}
stack<TreeNode*> st;
TreeNode* cur=root;
while (cur!= nullptr||!st.empty()){
if (cur!= nullptr){
st.push(cur);
cur=cur->left;
}else{
cur=st.top();
st.pop();
res.push_back(cur->val);
cur=cur->right;
}
}
}