当前位置:网站首页>先序遍历,中序遍历,后序遍历,层序遍历
先序遍历,中序遍历,后序遍历,层序遍历
2022-08-09 06:34:00 【未央吖】
先序遍历
递归:
class Solution {
public:
void preorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) {
return;
}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
preorder(root, res);
return res;
}
};
迭代:栈
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ret;
if (root) st.push(root);
while (!st.empty()) {
TreeNode*node = st.top();
st.pop();
ret.push_back(node->val); //中
if (node->right) st.push(node->right); //右
if (node->left) st.push(node->left); //左
}return ret;
}
};
中序遍历
递归:
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res); //左
res.push_back(root->val); //中
inorder(root->right, res); //右
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
};
迭代:栈
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
TreeNode*cur = root;
vector<int> ret;
while (cur || !st.empty()) {
while (cur) { //先遍历完所有左子树
st.push(cur);
cur = cur->left;
}
TreeNode*res = st.top();
st.pop();
ret.push_back(res->val); //中
cur = res->right; //右
}
return ret;
}
};
后序遍历
递归:
class Solution {
public:
void postorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) {
return;
}
postorder(root->left, res); //左
postorder(root->right, res); //右
res.push_back(root->val); //中
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
postorder(root, res);
return res;
}
};
迭代:栈
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int> ret;
if (root) st.push(root);
while (!st.empty()) {
TreeNode*cur = st.top();
ret.push_back(cur->val); //中
st.pop();
if (cur->left) {st.push(cur->left);} //左
if (cur->right) {st.push(cur->right);} //右
}
reverse(ret.begin(), ret.end()); //反转
return ret;
}
};
层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
if (!root) return ret;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
vector<int> res;
for (int i = 0; i < size; i++) {
TreeNode*cur = que.front();
que.pop();
res.push_back(cur->val);
if (cur->left) {que.push(cur->left);}
if (cur->right) {que.push(cur->right);}
}
ret.push_back(res);
}
return ret;
}
};
边栏推荐
猜你喜欢
治疗消化性溃疡—Toronto Research Chemicals 甘氨酸铝
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
ByteDance Interview Questions: Mirror Binary Tree 2020
Use of PlantUML plugin in idea
db.sqlite3没有“as Data Source“解决方法
C语言的内置宏(定义日志宏)
Likou Brush Question 180
Error jinja2.exceptions.UndefinedError: 'form' is undefined
static静态关键字和继承
workbench 数据导出
随机推荐
leetcode 之 70 爬楼梯问题 (斐波那契数)
Introduction of convenient functions and convenient shortcut keys of vs tomato assistant
简单工厂模式
jdepend
The singleton pattern
Xilinx Zynq ZynqMP DNA
Example of using the cut command
输入框最前面添加放大镜&&background-image和background-color冲突问题
2022.8.8DAY628
zip压缩包密码解密
idea中PlantUML插件使用
阿里巴巴官方技术号
移远EC20 4G模块拨号相关
ByteDance Written Exam 2020 (Douyin E-commerce)
Common Oracle Commands
AD picture PCB tutorial 20 minutes clear label shop operation process, copper network
workbench 数据导出
网络学习总结
Inception V3 闭眼检测
锁执行的过程