代码随想录算法训练营第36期DAY20

devtools/2024/9/25 2:30:17/

DAY20

110平衡二叉树

自己写的迭代法和递归都有问题,应该从:传入节点的树是否为平衡二叉树来考虑(大部分时候是subtree。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int subHei(TreeNode* node)
  15.     {
  16.         if(node==nullptrreturn 0;
  17.         int lsh=subHei(node->left),rsh=subHei(node->right);
  18.         if(lsh==-1return -1;
  19.         if(rsh==-1return -1;
  20.         if(abs(lsh-rsh)>1return -1;
  21.         else return 1+max(lsh,rsh);
  22.     }
  23.     bool isBalanced(TreeNode* root) {
  24.         return subHei(root)==-1?false:true;
  25.     }
  26. };

257二叉树的所有路径

中左右,所以前序遍历。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     void repath(TreeNode* root,vector<int> &path,vector<string>&res)
  15.     {
  16.         path.push_back(root->val);
  17.         if(root->left==nullptr&&root->right==nullptr)
  18.         {
  19.             string pathstring;
  20.             for(int i=0;i<path.size()-1;i++)
  21.             {
  22.                 pathstring+=to_string(path[i]);
  23.                 pathstring+="->";
  24.             }
  25.             pathstring+=to_string(path[path.size()-1]);
  26.             res.push_back(pathstring);
  27.             return;
  28.         }
  29.         if(root->left)repath(root->left,path,res),path.pop_back();
  30.         if(root->right)repath(root->right,path,res),path.pop_back();
  31.     }
  32.     vector<stringbinaryTreePaths(TreeNode* root) {
  33.         vector<int>path;
  34.         vector<string>res;
  35.         repath(root,path,res);
  36.         return res;
  37.     }
  38. };

404左叶子之和

没有想到用父节点来判断,作为核心逻辑。因为要知道孩子信息并且返回给父节点,那么用后序遍历。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int suml(TreeNode* root)
  15.     {
  16.         if(root==nullptrreturn 0;
  17.         int lval=0;
  18.         if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr)
  19.         lval=root->left->val;
  20.         return lval+suml(root->left)+suml(root->right);
  21.     }
  22.     int sumOfLeftLeaves(TreeNode* root) {
  23.         return suml(root);
  24.     }
  25. };

http://www.ppmy.cn/devtools/35756.html

相关文章

DS二叉搜索树

前言 我们在数据结构初阶专栏已经对二叉树进行了介绍并用C语言做了实现&#xff0c;但是当时没有对二叉搜树进行介绍&#xff0c;而是把他放到数据结构进阶构专栏的第一期来介绍&#xff0c;原因是后面的map和set&#xff08;红黑树&#xff09;是基于搜索树的&#xff0c;这里…

STM32编译前置条件配置

本文基于stm32f104系列芯片&#xff0c;记录编程代码前需要的操作&#xff1a; 添加库文件 在ST官网下载标准库STM32F10x_StdPeriph_Lib_V3.5.0&#xff0c;解压后&#xff0c;得到以下界面 启动文件 进入Libraries&#xff0c;然后进入CMSIS&#xff0c;再进入CM3&#xff…

正则表达式之python中re模块的使用以及一些习题

正则表达式 正则表达式是一种用来描述字符串模式的方法。它是一种强大的工具&#xff0c;用于在文本中搜索、匹配和编辑特定模式的字符串。正则表达式可以用来验证输入是否符合某种模式&#xff0c;提取文本中的特定信息&#xff0c;以及进行文本的替换和分割等操作。在计算机…

如何判断嵌入式平台OpenCV在使用硬件编解码器?

01 涉及OpenCV编解码库的一个命令行工具 python3 -c import cv2; print(cv2.getBuildInformation()) 它可以打印输出详细的OpenCV编译参数和当前的媒体库相关参数&#xff0c;我的rk3588打印的信息是这样的&#xff1a; catlubancat:~$ python3 -c import cv2; print(cv2.getBu…

《XXL_job技术文档》-分布式任务调度框架-双方式部署-tar.gz安装/docker安装

阿丹&#xff1a; 作为任务调度的使用&#xff0c;xxl_job是经常使用的&#xff0c;可以帮助程序员或者其他业务的定时任务变的可控。但是很多教程都是通过压缩包来进行运行和部署的&#xff0c;但是现在更多的都是将模块容器化。本文章一次性整理。 XXL-Job是一款开源的分布式…

牛客网刷题 | BC78 KiKi说祝福语

目前主要分为三个专栏&#xff0c;后续还会添加&#xff1a; 专栏如下&#xff1a; C语言刷题解析 C语言系列文章 我的成长经历 感谢阅读&#xff01; 初来乍到&#xff0c;如有错误请指出&#xff0c;感谢&#xff01; 描述 2020年来到了&#…

详细分析Java中的@AllArgsConstructor注解

目录 前言1. 基本知识2. 实战 前言 事情起因是Spring的循环依赖 详情可见&#xff1a;出现The dependencies of some of the beans in the application context form a cycle 解决方法&#xff08;全&#xff09; 1. 基本知识 AllArgsConstructor 是 Lombok 提供的一个注解…

java反射

一、什么是反射&#xff1f; 反射(Reflection) 反射就是&#xff1a;加载类&#xff0c;并允许以编程的方式解剖类中的各种成分(成员变量、方法、构造器等)。反射是一种强大的特性&#xff0c;允许程序在运行时检查和修改类、方法、字段等的信息&#xff0c;以及动态创建对象…