C++数据结构与算法——二叉树的属性

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

文章目录

  • 一、对称二叉树（力扣101）
  • 二、二叉树的最大深度（力扣104）
  • 三、二叉树的最小深度（力扣111）
  • 四、完全二叉树的节点个数（力扣222）
  • 五、平衡二叉树（力扣110）
  • 六、二叉树的所有路径（力扣257）
  • 七、左叶子之和（力扣404）
  • 八、找树左下角的值（513）
  • 九、路径总和（力扣112）

一、对称二叉树（力扣101）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return root;
        return isSymmetricLeftRight(root->left,root->right);
    }
    bool isSymmetricLeftRight(TreeNode* left,TreeNode* right){
        if(left==NULL&&right==NULL) return true;
        else if(left==NULL&&right!=NULL) return false;
        else if(left!=NULL&&right==NULL) return false;
        else if(left->val!=right->val) return false;
        else{
            bool outside = isSymmetricLeftRight(left->left,right->right);
            bool inside = isSymmetricLeftRight(left->right,right->left);
            if(outside!=true||inside!=true){
                return false;
            }
        }
        return true;
    }
};

在这里插入图片描述

二、二叉树的最大深度（力扣104）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        int result = 1+max(leftDepth,rightDepth);
        return result;
    }
};

在这里插入图片描述

三、二叉树的最小深度（力扣111）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL) return 0;
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);
        if (root->left == NULL && root->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (root->left != NULL && root->right == NULL) { 
            return 1 + leftDepth;
        }
        return min(leftDepth,rightDepth)+1;
    }
};

在这里插入图片描述

四、完全二叉树的节点个数（力扣222）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        int count=0;
        tr(root,count);
        return count;
    }
    void tr(TreeNode* root,int &count){
        if(root==NULL) return;
        tr(root->left,count);
        tr(root->right,count);
        count++;
    }
};

在这里插入图片描述

五、平衡二叉树（力扣110）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==NULL) return true;
        int result = getLength(root);
        if(result==-1) return false;
        return true;
    }
    int getLength(TreeNode* root){
        if(root==NULL) return 0;
        int leftLength = getLength(root->left);
        if(leftLength==-1) return -1;
        int rightLength = getLength(root->right);
        if(rightLength==-1) return -1;
        int result;
        if(abs(leftLength-rightLength)>1) return -1;
        else{
            result = max(rightLength,leftLength)+1;
        }
        return result;
    }
};

在这里插入图片描述

六、二叉树的所有路径（力扣257）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        traversal(root,path,result);
        return result;
    }
    void traversal(TreeNode * root,vector<int>& path,vector<string> &result){
        path.push_back(root->val);
        if(root->left==NULL&&root->right==NULL) {
            string temp;
            for(int i=0;i<path.size();i++){
                if(i==path.size()-1){
                    temp+= to_string(path[i]);
                }
                else{
                    temp+=to_string(path[i]);
                    temp+="->";
                }
            }
            result.push_back(temp);
            return;
        }
        if(root->left){
            traversal(root->left,path,result);
            path.pop_back();
        }
        if(root->right){
            traversal(root->right,path,result);
            path.pop_back();
        }

    }
};

在这里插入图片描述

七、左叶子之和（力扣404）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int sum=0;
        return trv(root,sum);
    }
    // 后续遍历
    int trv(TreeNode *root,int &sum){
        if(root==NULL) return 0;
        trv(root->left,sum);
        trv(root->right,sum);
        if(root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL){
            sum+= root->left->val;
        }
        return sum;
    }
};

在这里插入图片描述

八、找树左下角的值（513）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        vector<vector<int>> result = func(root);
        return result[result.size()-1][0];
    }
    // 层序遍历
    vector<vector<int>> func(TreeNode* root){
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            vector<int> vec;
            int Qsize=que.size();
            while(Qsize--){
                TreeNode * top = que.front();
                que.pop();
                vec.push_back(top->val);
                if(top->left) que.push(top->left);
                if(top->right) que.push(top->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

在这里插入图片描述

九、路径总和（力扣112）

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        vector<int> sumAll;
        vector<int> path;
        if(root==NULL) return false;
        traversal(root,path,sumAll);
        for(int i=0;i<sumAll.size();i++){
            if(sumAll[i]==targetSum){
                return true;
            }
        }
        return false;

    }
    void traversal(TreeNode*root,vector<int> &path,vector<int> &result){
        path.push_back(root->val);
        if(root->left==NULL&&root->right==NULL){
            int sum=0;
            for(int i=0;i<path.size();i++){
                sum+= path[i];
            }
            result.push_back(sum);
        }
        if(root->left) {
            traversal(root->left,path,result);
            path.pop_back();
        }
        if(root->right){
            traversal(root->right,path,result);
            path.pop_back();
        }
    }

};

在这里插入图片描述

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

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

相关文章

机器学习项目外包注意事项

机器学习项目外包注意事项

将机器学习项目外包给外部团队或合作伙伴是一种常见的做法&#xff0c;特别是当您的团队缺乏特定领域的专业知识或资源时。以下是一些关于机器学习项目外包的要点和注意事项&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#…
阅读更多...
【Unity】使用Unity实现双屏显示

【Unity】使用Unity实现双屏显示

引言 在使用Unity的时候&#xff0c;有时候会需要使用双屏显示 简单来说就是需要在两个显示器中显示游戏画面 双屏显示注意点&#xff1a; ①双屏显示需要电脑有两个显示 ②双屏显示只能用于PC端 ③不仅仅可以双屏&#xff0c;Unity最大支持8屏显示 1.相机设置 ①我们打开Un…
阅读更多...
[VNCTF2024]-PWN:preinit解析（逆向花指令，绕过strcmp，函数修改，机器码）

[VNCTF2024]-PWN:preinit解析（逆向花指令，绕过strcmp，函数修改，机器码）

查看保护&#xff1a; 查看ida&#xff1a; 这边其实看反汇编没啥大作用&#xff0c;需要自己动调。 但是前面的绕过strcmp还是要看一下的。 解题&#xff1a; 这里是用linux自带的产生随机数的文件urandom来产生一个随机密码&#xff0c;然后让我们输入密码&#xff0c;用st…
阅读更多...
【论文笔记】An Effective Adversarial Attack on Person Re-Identification ...

【论文笔记】An Effective Adversarial Attack on Person Re-Identification ...

原文标题&#xff08;文章标题处有字数限制&#xff09;&#xff1a; 《An Effective Adversarial Attack on Person Re-Identification in Video Surveillance via Dispersion Reduction》 Abstract 通过减少神经网络内部特征图的分散性攻击reid模型。 erbloo/Dispersion_r…
阅读更多...
【C语言】常见的动态内存管理错误

【C语言】常见的动态内存管理错误

前言 上一篇介绍了C语言中 动态内存管理函数&#xff0c;本片讲解的是 在我们使用动态内存管理时 常见的错误&#xff0c;一起来看看吧~ 欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 目录 1.对NULL指针的解引⽤操作 错…
阅读更多...
深入解析Golang的encoding/ascii85库：从基础到实战

深入解析Golang的encoding/ascii85库：从基础到实战

深入解析Golang的encoding/ascii85库&#xff1a;从基础到实战 引言基础知识什么是ASCII85编码&#xff1f;ASCII85编码的工作原理ASCII85编码的优点ASCII85编码的缺点 使用Golang的encoding/ascii85库引入encoding/ascii85包ASCII85编码ASCII85解码实战示例小结 进阶技巧和最佳…
阅读更多...
Vue3(pinia) 整合 SpringWebsocket链接url动态传参

Vue3(pinia) 整合 SpringWebsocket链接url动态传参

前言&#xff1a; &#x1f44f;作者简介&#xff1a;我是笑霸final&#xff0c;一名热爱技术的在校学生。 &#x1f4dd;个人主页&#xff1a;个人主页1 || 笑霸final的主页2 &#x1f4d5;系列专栏&#xff1a;java专栏 &#x1f4e7;如果文章知识点有错误的地方&#xff0c;…
阅读更多...
轧辊品质检测 直线度测量仪满足多种数据监测！

轧辊品质检测 直线度测量仪满足多种数据监测！

轧辊有带钢轧辊、型钢轧辊、线材轧辊、开坯辊、粗轧辊、精轧辊、破鳞辊、穿孔辊、平整辊、钢轧辊、铸铁轧辊、硬质合金轧辊、陶瓷轧辊等&#xff0c;但不管哪种类型的轧辊&#xff0c;对直线度测量都可以通过直线度测量仪来实现&#xff0c;这种测量仪检测方便&#xff0c;数据…
阅读更多...
现货黄金贵金属投资难不难做？

现货黄金贵金属投资难不难做？

现货黄金投资的难度因人而异&#xff0c;它涉及市场知识、分析能力、资金管理和心理素质等多个方面&#xff0c;因此不能一概而论。但是&#xff0c;如果投资者能够系统地学习相关知识&#xff0c;并在实践中不断积累经验&#xff0c;那么现货黄金投资并非难以驾驭。 先了解现货…
阅读更多...
《汇编语言》- 读书笔记 - 第13章-int 指令

《汇编语言》- 读书笔记 - 第13章-int 指令

《汇编语言》- 读书笔记 - 第13章-int 指令 13.1 int 指令13.2 编写供应用程序调用的中断例程中断例程&#xff1a;求一 word 型数据的平方主程序中断处理程序执行效果 中断例程&#xff1a;将一个全是字母&#xff0c;以0结尾的字符串&#xff0c;转化为大写主程序中断处理程序…
阅读更多...
作业1-224——P1927 防护伞

作业1-224——P1927 防护伞

思路 遍历一下找到两点间的最远距离&#xff0c;直接公式算结果&#xff0c;控制输出位数 参考代码 #include<iostream> #include<iomanip> #include<cmath> using namespace std; int main() { int n; cin>>n; int x[n],y[n]; do…
阅读更多...
hive报错：FAILED: NullPointerException null

hive报错：FAILED: NullPointerException null

发现问题 起因是我虚拟机的hive不管执行什么命令都报空指针异常的错误 我也在网上找了很多相关问题的资料&#xff0c;发现都不是我这个问题的解决方法&#xff0c;后来在hive官网上与hive 3.1.3版本相匹配的hadoop版本是3.x的版本&#xff0c;而我的hadoop版本还是2.7.2的版本…
阅读更多...
5G 网络建设【华为OD机试-JAVAPythonC++JS】

5G 网络建设【华为OD机试-JAVAPythonC++JS】

题目描述 现需要在某城市进行5G网络建设&#xff0c;已经选取N个地点设置5G基站&#xff0c;编号固定为1到N&#xff0c;接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通&#xff0c;不同基站之间架设光纤的成本各不相同&#xff0c;且有些节点之间已经存在光纤相…
阅读更多...
WIN10 无密码自动登录

WIN10 无密码自动登录

1、家里重装了一下WIN10系统&#xff0c;第一次登陆居然用了微软网站账号&#xff0c;结果密码忘记了&#xff0c;后面只能用PIN码登陆系统。 2、需要登录微软的网站修改密码&#xff1a; Microsoft account | Sign In or Create Your Account Today – Microsoft 3、在运行…
阅读更多...
赵本山与高秀敏夫妇本想找范伟要那1200元电视机垫款，却不好意思向范伟开口--小品《面子》（中1）的台词

赵本山与高秀敏夫妇本想找范伟要那1200元电视机垫款，却不好意思向范伟开口--小品《面子》（中1）的台词

赵本山与高秀敏夫妇本想找范伟要那1200元电视机垫款&#xff0c;却不好意思向范伟开口 --小品《面子》&#xff08;中1&#xff09;的台词 表演者&#xff1a;赵本山 高秀敏 范伟 &#xff08;接上&#xff09; 高秀敏&#xff1a;咱俩抓紧提事啊 赵本山&#xff1a;不着急…
阅读更多...
div在vue的组件之中如何设置这个字体的颜色和样式大小

div在vue的组件之中如何设置这个字体的颜色和样式大小

在Vue组件中设置<div>的字体颜色和样式大小可以通过两种主要方式实现&#xff1a;通过内联样式&#xff08;inline styles&#xff09;或者通过CSS类&#xff08;CSS classes&#xff09;。 使用内联样式 在Vue模板中直接在元素上使用style属性来设置样式。这种方法适用…
阅读更多...
上云还是下云，最大挑战是什么？| 对话章文嵩、毕玄、王小瑞

上云还是下云，最大挑战是什么？| 对话章文嵩、毕玄、王小瑞

近半年来&#xff0c;公有云领域频频发生阿里云、滴滴等平台崩溃事件&#xff0c;与此同时&#xff0c;马斯克的“X 下云省钱”言论引起了广泛关注&#xff0c;一时间&#xff0c;“上云”和“下云”成为热议话题。在最近举办的 AutoMQ 云原生创新论坛上&#xff0c;AutoMQ 联合…
阅读更多...
【GPU驱动开发】- AST简介

【GPU驱动开发】- AST简介

前言 不必害怕未知&#xff0c;无需恐惧犯错&#xff0c;做一个Creator&#xff01; AST&#xff0c;抽象语法树&#xff0c;是一种包含丰富语义信息的格式&#xff0c;其中包括类型、表达式树和符号等。 TranslationUnitDecl&#xff1a;该类表示一个输入源文件 ASTContext&…
阅读更多...
通辽文化瑰宝沈阳展，文物预防性保护成亮点

通辽文化瑰宝沈阳展，文物预防性保护成亮点

灿烂的历史瑰宝&#xff0c;从通辽草原远道而来&#xff0c;于沈阳博物馆内熠熠生辉。展览汇聚了非常多的历史文物&#xff0c;每一件都承载着深厚的文化底蕴和民族记忆。但是&#xff0c;文物的易损性变成一个大问题。为了确保这些历史财产可以在最佳状态下向群众展现&#xf…
阅读更多...
如何在腾讯云上快速部署幻兽帕鲁/Palworld服务器？

如何在腾讯云上快速部署幻兽帕鲁/Palworld服务器？

如何在腾讯云上快速部署幻兽帕鲁/Palworld服务器&#xff1f; 准备工作&#xff1a;首先需要准备腾讯云账号和Steam账号。腾讯云账号适用于新老用户&#xff0c;而Steam账号则是因为幻兽帕鲁是一款Steam平台的游戏。此外&#xff0c;还需要购买一台腾讯云服务器&#xff0c;推荐…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站