LeetCode：二叉树-北京尧图网络

文章目录572.另一棵树的子树662.二叉树最大宽度129.求根节点到叶子节点数字之和102.二叉树的层序遍历572.另一棵树的子树给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。【思路】如果root所在树和subRoot所在树完全相同则直接返回true否则就分别判断root的左子树和右子树是否和subRoot所在树完全相同classSolution{public:boolisSametree(TreeNode*p,TreeNode*q){if(pnullptrqnullptr)returntrue;//终止条件if(pqp-valq-val){returnisSametree(p-left,q-left)isSametree(p-right,q-right);}else{returnfalse;//终止条件}}boolisSubtree(TreeNode*root,TreeNode*subRoot){if(!root){returnfalse;//终止条件}if(isSametree(root,subRoot)){returntrue;//终止条件}returnisSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);}};662.二叉树最大宽度给你一棵二叉树的根节点 root 返回树的最大宽度。树的最大宽度是所有层中最大的宽度。每一层的宽度被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。【思路】完全二叉树节点编号特性根id左孩子2id右孩子2id1DFS遍历时记录每层第一个访问到的最左节点编号到vec不断更细最大值当前节点编号- 本层最左编号 1classSolution{private:intmaxW0;vectorintfirstIds;public:intwidthOfBinaryTree(TreeNode*root){dfs(root,1,0);returnmaxW;}voiddfs(TreeNode*node,intid,intdepth){if(nodenullptr)return;// 第一次到达这一层记录最左节点编号if(firstIds.size()depth){firstIds.push_back(id);}// 更新最大宽度maxWmax(maxW,id-firstIds[depth]1);// 遍历左右子树dfs(node-left,id*2,depth1);dfs(node-right,id*21,depth1);}};129.求根节点到叶子节点数字之和给你一个二叉树的根节点 root 树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字例如从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。计算从根节点到叶节点生成的所有数字之和。叶节点是指没有子节点的节点。【思路】dfs深度优先遍历preSum * 10 node-val乘10是关键classSolution{public:intdfs(TreeNode*root,intpreSum){if(rootnullptr)return0;intsumpreSum*10root-val;//核心!if(root-leftnullptrroot-rightnullptr){returnsum;}else{returndfs(root-left,sum)dfs(root-right,sum);}}intsumNumbers(TreeNode*root){returndfs(root,0);}};102.二叉树的层序遍历给你二叉树的根节点 root 返回其节点值的层序遍历。即逐层地从左到右访问所有节点【思路】queue存放节点怎么区分每层BFS循环当队列queue为空时跳出建立一个临时vector用于存储当前层数据循环当前层循环次数为当前层的节点数!!!核心- 出队列首元素出队即为node- tmp存储- 添加子节点若node的左右子节点不为空则将其加入队列queue

LeetCode：二叉树

相关推荐

FRP内网穿透实战：从零部署稳定HTTPS隧道

linux笔记归纳9：进程间通信

Win11 24H2安装.NET 3.5的解决方案与兼容性处理

更多资讯

基于YOLOv5与ResNet18的手骨X光片骨龄检测系统实践

Docker生产环境应急处理指南：故障排查与常用命令速查

多Rail NCCL排障指南：GPU-NIC亲和性、HCA选择与逐Rail验证

专科生AI论文软件实测：8款工具从选题到降重的搭配指南

嵌入式Linux Modbus RTU串口通信从配置到实战

二叉树递归四大经典问题解析与优化技巧

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？