一、二叉树的前序遍历
1.题目
Leetcode:第 144 题
给你二叉树的根节点 root
,返回它节点值的 前序 遍历。
示例 1:
输入:root = [1,null,2,3] 输出:[1,2,3]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
示例 4:
输入:root = [1,2] 输出:[1,2]
示例 5:
输入:root = [1,null,2] 输出:[1,2]
2.解题思路
迭代法和递归法
3.实现代码
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
// 定义一个结构体TreeNode,用于表示二叉树的节点。
struct TreeNode {
int val; // 存储节点的值。
TreeNode* left; // 指向该节点左子树的指针。
TreeNode* right; // 指向该节点右子树的指针。
// TreeNode的构造函数,用于创建一个TreeNode实例。
// 参数x是节点的值,left和right默认为NULL,表示没有左右子节点。
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//一、二叉树的前序遍历(递归法)
class Solution1 {
public:
// 定义一个名为traversal的成员函数,用于执行二叉树的递归遍历。
// 参数cur是当前遍历到的TreeNode指针,参数vec是一个引用,用于存储遍历结果。
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) { // 如果当前节点为空,则直接返回,不再继续遍历。
return;
}
vec.push_back(cur->val); // 访问当前节点,将其值添加到容器vec中。
traversal(cur->left, vec); // 递归遍历左子树。
traversal(cur->right, vec); // 递归遍历右子树。
}
// 定义一个名为preorderTraversal的成员函数,用于返回二叉树的前序遍历结果,参数root是二叉树的根节点指针。
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result; // 创建一个空容器,用于存储前序遍历的结果。
traversal(root, result); // 调用traversal函数,传入根节点root和容器result的引用,执行前序遍历。
return result; // 返回结果。
}
};
//二、二叉树的前序遍历(迭代法)
class Solution2 {
public:
// 定义名为preorderTraversal的成员函数,接受一个指向TreeNode的指针作为参数。
// 函数的目的是返回一个包含二叉树前序遍历结果的容器。
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result; // 创建一个空的整数向量result,用于存储前序遍历的结果。
stack<TreeNode*> st;// 创建一个空的栈st,用于辅助进行前序遍历。
if (root != NULL) {// 检查传入的二叉树根节点是否为空。
st.push(root);// 如果根节点不为空,则将其压入栈中。
}
while (!st.empty()) { // 使用while循环进行遍历,直到栈为空。
TreeNode* node = st.top();// 从栈顶取出当前节点指针。
if (node != NULL) { // 检查当前节点是否为空。
st.pop(); // 如果当前节点不为空,则将其从栈中弹出。
if (node->right) {// 如果当前节点的右子节点不为空,则将其压入栈中。
st.push(node->right);// 如果当前节点的左子节点不为空,则将其压入栈中。
}
if (node->left) {
st.push(node->left);
}
st.push(node);// 将当前节点再次压入栈中,这样做是为了在后续的遍历中能够访问到根节点。
st.push(NULL); // 压入一个空指针作为前序遍历的分隔符。
}
else {// 如果node为空,说明栈顶元素是NULL,这表示已经处理完一个节点的左右子树
st.pop();// 弹出栈顶元素(此时是NULL)
node = st.top();// 获取当前节点。
st.pop();// 弹出当前节点,并将其值添加到结果中。
result.push_back(node->val);
}
}
return result;// 返回包含前序遍历结果。
}
};
//测试
// 辅助函数,用于创建一个新的TreeNode
TreeNode* createNode(int value) {
return new TreeNode(value);
}
// 辅助函数,用于构建二叉树
TreeNode* buildTree(vector<int>& values) {
if (values.empty()) return NULL;
TreeNode* root = createNode(values[0]);
queue<TreeNode*> queueNode;
queueNode.push(root);
int i = 1;
while (!queueNode.empty()) {
TreeNode* node = queueNode.front();
queueNode.pop();
if (i < values.size()) {
node->left = createNode(values[i++]);
queueNode.push(node->left);
}
if (i < values.size()) {
node->right = createNode(values[i++]);
queueNode.push(node->right);
}
}
return root;
}
// 打印容器中的所有元素,用于验证测试结果
void printVector(const vector<int>& vec) {
for (int value : vec) {
cout << value << " ";
}
cout << endl;
}
// 主函数
int main() {
vector<int> treeValues = { 1, 2, 3, 4, 5, 6, 7 };// 定义二叉树的层序遍历结果,用于构建二叉树
TreeNode* root = buildTree(treeValues); // 构建二叉树
Solution1 s1;// 创建Solution类的实例
Solution2 s2;
vector<int> result1 = s1.preorderTraversal(root);// 传入二叉树的根节点
vector<int> result2 = s2.preorderTraversal(root);
// 打印中序遍历的结果
cout << "二叉树的前序遍历(递归法)结果是: ";
printVector(result1);
cout << endl;
cout << "二叉树的前序遍历(迭代法)结果是: ";
printVector(result2);
cout << endl;
return 0;
}
二、二叉树的中序遍历
1.题目
Leetcode:第 94 题
给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[1,3,2]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
2.解题思路
迭代法和递归法
3.实现代码
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
// 定义一个结构体TreeNode,用于表示二叉树的节点。
struct TreeNode {
int val; // 存储节点的值。
TreeNode* left; // 指向该节点左子树的指针。
TreeNode* right; // 指向该节点右子树的指针。
// TreeNode的构造函数,用于创建一个TreeNode实例。
// 参数x是节点的值,left和right默认为NULL,表示没有左右子节点。
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//一、二叉树的中序遍历(递归法)
class Solution1 {
public:
// 定义一个名为traversal的成员函数,用于执行二叉树的递归遍历。
// 参数cur是当前遍历到的TreeNode指针,参数vec是一个引用,用于存储遍历结果。
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) { // 如果当前节点为空,则直接返回,不再继续遍历。
return;
}
traversal(cur->left, vec);// 递归遍历左子树。
vec.push_back(cur->val); // 访问当前节点,将其值添加到容器vec中。
traversal(cur->right, vec);// 递归遍历右子树。
}
// 定义一个名为inorderTraversal的成员函数,用于返回二叉树的中序遍历结果,参数root是二叉树的根节点指针。
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result; // 创建一个空容器,用于存储中序遍历的结果。
traversal(root, result); // 调用traversal函数,传入根节点root和容器result的引用,执行中序遍历。
return result; // 返回结果。
}
};
//二、二叉树的中序遍历(迭代法)
class Solution2 {
public:
// inorderTraversal函数用于实现中序遍历
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result; // 存储遍历结果的数组
stack<TreeNode*> st; // 定义一个栈,用于辅助中序遍历
if (root != NULL) {// 如果根节点不为空,则将其入栈
st.push(root);
}
while (!st.empty()) {// 当栈不为空时,循环执行以下操作
TreeNode* node = st.top();// 获取栈顶元素
if (node != NULL) { // 如果node不为空
st.pop(); // 弹出栈顶元素
if (node->right) {// 如果node有右子节点,先将右子节点入栈
st.push(node->right);
}
st.push(node); // 将当前节点再次压入栈中,这样做是为了在后续的遍历中能够访问到根节点。
st.push(NULL); // 压入一个空指针作为中序遍历的分隔符。
if (node->left) {// 如果node有左子节点,将左子节点入栈
st.push(node->left);
}
}
else {// 如果node为空,说明栈顶元素是NULL,这表示已经处理完一个节点的左右子树
st.pop();// 弹出栈顶元素(此时是NULL)
node = st.top();// 获取当前节点。
st.pop();// 弹出当前节点,并将其值添加到结果中。
result.push_back(node->val);
}
}
return result; // 返回中序遍历的结果
}
};
//测试
// 辅助函数,用于创建一个新的TreeNode
TreeNode* createNode(int value) {
return new TreeNode(value);
}
// 辅助函数,用于构建二叉树
TreeNode* buildTree(vector<int>& values) {
if (values.empty()) return NULL;
TreeNode* root = createNode(values[0]);
queue<TreeNode*> queueNode;
queueNode.push(root);
int i = 1;
while (!queueNode.empty()) {
TreeNode* node = queueNode.front();
queueNode.pop();
if (i < values.size()) {
node->left = createNode(values[i++]);
queueNode.push(node->left);
}
if (i < values.size()) {
node->right = createNode(values[i++]);
queueNode.push(node->right);
}
}
return root;
}
// 打印容器中的所有元素,用于验证测试结果
void printVector(const vector<int>& vec) {
for (int value : vec) {
cout << value << " ";
}
cout << endl;
}
// 主函数
int main() {
vector<int> treeValues = { 1, 2, 3, 4, 5, 6, 7 };// 定义二叉树的层序遍历结果,用于构建二叉树
TreeNode* root = buildTree(treeValues); // 构建二叉树
Solution1 s1;// 创建Solution类的实例
Solution2 s2;
vector<int> result1 = s1.inorderTraversal(root);// 传入二叉树的根节点
vector<int> result2 = s2.inorderTraversal(root);
cout << "二叉树的中序遍历(递归法)结果是: ";
printVector(result1);
cout << endl;
cout << "二叉树的中序遍历(迭代法)结果是: ";
printVector(result2);
cout << endl;
return 0;
}
三、二叉树的后序遍历
1.题目
Leetcode:第 145 题
给你一棵二叉树的根节点 root
,返回其节点值的 后序遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[3,2,1]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
2.解题思路
迭代法和递归法
3.实现代码
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
// 定义一个结构体TreeNode,用于表示二叉树的节点。
struct TreeNode {
int val; // 存储节点的值。
TreeNode* left; // 指向该节点左子树的指针。
TreeNode* right; // 指向该节点右子树的指针。
// TreeNode的构造函数,用于创建一个TreeNode实例。
// 参数x是节点的值,left和right默认为NULL,表示没有左右子节点。
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//一、二叉树的后序遍历(递归法)
class Solution1 {
public:
// 定义一个名为traversal的成员函数,用于执行二叉树的递归后序遍历。
// 参数cur是当前遍历到的TreeNode指针,参数vec是一个引用,用于存储遍历结果。
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) { // 如果当前节点为空,则返回,不执行任何操作。
return;
}
traversal(cur->left, vec); // 递归调用traversal函数遍历当前节点的左子树。
traversal(cur->right, vec); // 递归调用traversal函数遍历当前节点的右子树。
vec.push_back(cur->val);// 访问当前节点,将其值添加到容器vec中。
}
// 定义一个名为postorderTraversal的成员函数,用于返回二叉树的后序遍历结果,参数root是二叉树的根节点指针。
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result; // 创建一个空容器,用于存储后序遍历的结果。
traversal(root, result); // 调用traversal函数,传入根节点root和容器result的引用,执行后序遍历。
return result; // 返回结果。
}
};
//二、二叉树的后序遍历(迭代法)
class Solution2 {
public:
// postorderTraversal函数用于实现后序遍历
vector<int> postorderTraversal(TreeNode* root){
vector<int> result; // 存储遍历结果的数组
stack<TreeNode*> st; // 定义一个栈,用于辅助中序遍历
if (root != NULL) {// 如果根节点不为空,则将其入栈
st.push(root);
}
while (!st.empty()) {// 当栈不为空时,循环执行以下操作
TreeNode* node = st.top();// 获取栈顶元素
if (node != NULL) { // 如果node不为空
st.pop(); // 弹出栈顶元素
st.push(node); // 将当前节点再次压入栈中,这样做是为了在后续的遍历中能够访问到根节点。
st.push(NULL); // 压入一个空指针作为后序遍历的分隔符。
if (node->right) {// 如果node有右子节点,先将右子节点入栈
st.push(node->right);
}
if (node->left) {// 如果node有左子节点,将左子节点入栈
st.push(node->left);
}
}
else {// 如果node为空,说明栈顶元素是NULL,这表示已经处理完一个节点的左右子树
st.pop();// 弹出栈顶元素(此时是NULL)
node = st.top();// 获取当前节点。
st.pop();// 弹出当前节点,并将其值添加到结果中。
result.push_back(node->val);
}
}
return result; // 返回后序遍历的结果
}
};
//测试
// 辅助函数,用于创建一个新的TreeNode
TreeNode* createNode(int value) {
return new TreeNode(value);
}
// 辅助函数,用于构建二叉树
TreeNode* buildTree(vector<int>& values) {
if (values.empty()) return NULL;
TreeNode* root = createNode(values[0]);
queue<TreeNode*> queueNode;
queueNode.push(root);
int i = 1;
while (!queueNode.empty()) {
TreeNode* node = queueNode.front();
queueNode.pop();
if (i < values.size()) {
node->left = createNode(values[i++]);
queueNode.push(node->left);
}
if (i < values.size()) {
node->right = createNode(values[i++]);
queueNode.push(node->right);
}
}
return root;
}
// 打印容器中的所有元素,用于验证测试结果
void printVector(const vector<int>& vec) {
for (int value : vec) {
cout << value << " ";
}
cout << endl;
}
// 主函数
int main() {
vector<int> treeValues = { 1, 2, 3, 4, 5, 6, 7 };// 定义二叉树的层序遍历结果,用于构建二叉树
TreeNode* root = buildTree(treeValues); // 构建二叉树
Solution1 s1;// 创建Solution类的实例
Solution2 s2;
vector<int> result1 = s1.postorderTraversal(root);// 传入二叉树的根节点
vector<int> result2 = s2.postorderTraversal(root);
cout << "二叉树的后序遍历(递归法)结果是: ";
printVector(result1);
cout << endl;
cout << "二叉树的后序遍历(迭代法)结果是: ";
printVector(result2);
cout << endl;
return 0;
}
ps:以上皆是本人在探索算法世界旅途中的浅薄见解,诚挚地希望得到各位的宝贵意见与悉心指导,若有不足或谬误之处,还请多多指教。