Leetcode算法训练日记 | day14

一、二叉树的前序遍历

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:以上皆是本人在探索算法世界旅途中的浅薄见解,诚挚地希望得到各位的宝贵意见与悉心指导,若有不足或谬误之处,还请多多指教。 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532513.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

wps可以打钩的框框

方法一&#xff1a; 输入2611&#xff0c;按下altx 方法二&#xff1a; R 选中后->开始->字体wingdings字体

MATLAB 点云体素滤波 (58)

MATLAB 体素滤波 (58) 一、基本原理二、算法实现1.代码数据的海量性始终是点云处理时需要面临的一个大问题,严重的时间消耗和内存占用影响了点云处理的发展,当然了,点云数量主要应该看项目的实际需求,若是对细节要求较高,那么点云数量不可过少,但是要求过低时,我们就可…

番外篇 | YOLOv8改进之引入YOLOv9的ADown模块 | 替换YOLOv8卷积

前言:Hello大家好,我是小哥谈。YOLOv9是一种目标检测算法,而ADown模块是YOLOv9中的一个重要组成部分。ADown模块主要用于特征提取和下采样操作,以便在后续的检测任务中更好地捕捉目标的特征。具体来说,ADown模块是YOLOv9中的一个卷积块,由一系列卷积层和池化层组成。它的…

Linux网卡:连接虚拟与现实的桥梁

在介绍Linux网卡之前&#xff0c;让我们先迈入时光机&#x1f570;️&#xff0c;回到1980年代末期&#xff0c;互联网正在逐步从一个科研网络向公众网络转变&#xff0c;Linux——一个自由和开源的操作系统诞生了&#x1f427;。Linux的出现&#xff0c;对于计算机科学领域来说…

B端:发起个申请,审批慢如蜗牛,那是你不懂高效审批流程设计。

有时候我们发起个申请&#xff0c;让领导和上级审批&#xff0c;迟迟不见动静&#xff0c;又不好一直催促领导&#xff0c;或者领导不会操作&#xff0c;误操作&#xff0c;怎么办&#xff0c;其实你是缺乏高效的流程设计。 设计一个高效的审批流程对于B端系统非常重要&#x…

Unity核心学习

目录 认识模型的制作流程模型的制作过程 2D相关图片导入设置图片导入概述纹理类型设置纹理形状设置纹理高级设置纹理平铺拉伸设置纹理平台打包相关设置 SpriteSprite Editor——Single图片编辑Sprite Editor——Multiple图片编辑Sprite Editor——Polygon图片编辑SpriteRendere…

高精度地图导航论文汇总

文章目录 2022基于高精度地图的智能车辆路径规划与跟踪控制研究[M] 2023一种无人驾驶融合决策方案的设计与实现[M] 2022 基于高精度地图的智能车辆路径规划与跟踪控制研究[M] 摘要&#xff1a; 随着计算机及通信技术的不断进步&#xff0c;汽车行业也得到了飞速的发展。汽车在…

ZStack Cloud 5.0.0正式发布——Vhost主存储、隔离PVLAN网络、云平台报警优化、灰度升级增强四大亮点简析

近日&#xff0c;ZStack Cloud 5.0.0正式发布&#xff0c;推出了包含Vhost主存储、隔离PVLAN网络、云平台报警优化、灰度升级增强在内的一系列重要功能。云主机管理、物理机运维、密评合规、灾备服务等诸多使用场景和功能模块均有更新&#xff0c;为您带来更完善的平台服务、更…

机器人坐标系转换从局部坐标系转换到世界坐标系

矩阵方式&#xff1a; 下面是代码&#xff1a; #include <Eigen/Dense>static void transLocalToWorldCloudWith2dPose(const PointCloud &pc_tar, const QPose3f &pose, PointCloud &pc_org) {if (pc_tar.empty())return;PointCloud tmp_pc;Eigen::Rotati…

解读POP3:电子邮件查看必备技巧揭秘

在您点击阅读时&#xff0c;是否曾想过您是如何如此轻松地查看电子邮件的&#xff1f;对我们来说&#xff0c;这听起来可能只是几秒钟的加载时间&#xff0c;但实际上幕后发生了许多事情。邮局协议&#xff08;POP3&#xff09;是一种应用层协议&#xff0c;电子邮件客户端使用…

基于Android的记单词App系统的设计与实现

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…

Linkedin领英封号原因是什么?如何养号?

领英作为全球最大的职场社交平台&#xff0c;用户总数已超过8亿&#xff0c;覆盖200多个国家和地区&#xff0c;中国会员总数也已经累计超过5700万&#xff0c;庞大的基数使得他迅速成为跨境业务员建立形象&#xff0c;拓展人脉&#xff0c;开发客户的重要渠道。“领英职场”的…

C语言面试题之检查二叉树平衡性

检查二叉树平衡性 实例要求 1、实现一个函数&#xff0c;检查二叉树是否平衡&#xff1b;2、在这个问题中&#xff0c;平衡树的定义如下&#xff1a;任意一个节点&#xff0c;其两棵子树的高度差不超过 1&#xff1b; 示例 1: 给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/…

【PyQt5篇】和子线程进行通信

文章目录 &#x1f354;使用QtDesigner进行设计&#x1f6f8;和子线程进行通信&#x1f388;运行结果 &#x1f354;使用QtDesigner进行设计 我们首先使用QtDesigner设计界面 得到代码login.ui <?xml version"1.0" encoding"UTF-8"?> <ui …

如何保证消息不丢失?——使用rabbitmq的死信队列!

如何保证消息不丢失?——使用rabbitmq的死信队列&#xff01; 1、什么是死信 在 RabbitMQ 中充当主角的就是消息&#xff0c;在不同场景下&#xff0c;消息会有不同地表现。 死信就是消息在特定场景下的一种表现形式&#xff0c;这些场景包括&#xff1a; 消息被拒绝访问&am…

c/c++函数: strtok() ,strtok_s()

概述 函数的原型&#xff1a; char* strtok : strtok (char* _String, char const* _Delimiter); char* strtok_s: strtok_s( char* _String, char const* _Delimiter, char** _Context);函数的参数: _String : 传入一个字符串 _Delimiter: 传入一个字符字…

【canvas】canvas基础使用(四):线型的设置

简言 学习如何使用canvas来设置线形。 线型的方法和属性 使用canvas经常会和线段打交道&#xff0c;下面是设置线型的常用属性和方法。 lineWidth 线宽 CanvasRenderingContext2D.lineWidth 是 Canvas 2D API 设置线段厚度的属性&#xff08;即线段的宽度&#xff09;。 线…

VR紧急情况模拟|V R体验中心加盟|元宇宙文旅

通过VR技术实现紧急情况模拟&#xff0c;提升安全应急能力&#xff01; 简介&#xff1a;面对突发紧急情况&#xff0c;如火灾、地震、交通事故等&#xff0c;正确的反应和应对能够有效减少伤害和损失。为了提高人们在紧急情况下的应急能力&#xff0c;我们借助先进的虚拟现实…

全国水科技大会 免费征集《水环境治理减污降碳协同增效示范案例》

申报时间截止到2024年4月15日&#xff0c;请各单位抓紧申报&#xff0c;申报条件及申报表请联系&#xff1a;13718793867 围绕水环境治理减污降碳协同增效领域&#xff0c;以资源化、生态化和可持续化为导向&#xff0c;面向生态、流城、城市、农村、工业园区、电力、石化、钢…

寄快递的省钱小妙招,看看你能知道多少

首先就是从包裹的重量上和体积上&#xff0c;我们都知道快递员上门取件都是需要称重的&#xff0c;我们能做的就是尽量压缩包裹的体积来减少快递的运费价格。然后是使用自己的包装袋来打包行李&#xff0c;快递员的袋子也是需要另外花费的。对于一些不容易损坏的货物来说&#…