当前位置: 首页 > news >正文

算法日记 13 day 二叉树

今天继续二叉树啊!!!

题目:平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode)

给定一个二叉树,判断它是否是 平衡二叉树

   题目分析:

        平衡二叉树指的是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

在之前的题中,我们做过了求树的最大深度,不过我们使用的是求高度的写法,通过后序遍历的方式将子节点的高度返回给父节点。同样的,平衡二叉树的判断也是这种方式。

public class Solution {public bool IsBalanced(TreeNode root) {return (GetHeight(root)==-1)?false:true;}public int GetHeight(TreeNode root){if(root==null) return 0;int left=GetHeight(root.left);//使用后序遍历,这样能够将子节点的信息返回给父节点if(left==-1) return-1;int right=GetHeight(root.right);if(right==-1) return-1;int res;if(Math.Abs(left-right)>1)//左右子树的高度差{res=-1;}else{res=1+Math.Max(left,right);}return res;}
}

 题目:二叉树的所有路径

257. 二叉树的所有路径 - 力扣(LeetCode)

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]
 题目分析:       

这道题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。

在这道题目中将第一次涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。记住回溯是需要回退的。

回溯的本质其实就是递归,所以写法上和递归差不多。

public class Solution {public IList<string> BinaryTreePaths(TreeNode root) {List<int> path=new List<int>();List<string> res=new List<string>();if (root == null) return res;BrackTracing(root,path,res);return res;}public void BrackTracing(TreeNode root,List<int> path,List<string> res){path.Add(root.val);//记录当前的节点if(root.right==null&&root.left==null)//叶子节点{string str="";for(int i=0;i<path.Count-1;i++){str+=path[i].ToString();str+="->";}str+=path[path.Count-1].ToString();res.Add(str);}if(root.left!=null){BrackTracing(root.left,path,res);path.RemoveAt(path.Count-1);//回退一个节点}if(root.right!=null){BrackTracing(root.right,path,res);path.RemoveAt(path.Count-1);}}
}

题目:左叶子之和

404. 左叶子之和 - 力扣(LeetCode)

给定二叉树的根节点 root ,返回所有左叶子之和。

示例 1:

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
题目分析: 

        这个左叶子是指节点A的左孩子不为空,且左孩子的左右孩子都为空(说明是叶子节点),那么A节点的左孩子为左叶子节点。所有我们应该是通过父节点去判断左子节点是否为左叶子节点

public class Solution {public int SumOfLeftLeaves(TreeNode root) {if(root==null) return 0;int left=SumOfLeftLeaves(root.left);if (root.left!=null && root.left.left==null && root.left.right==null){// 左子树就是一个左叶子的情况left+=root.left.val;}int right=SumOfLeftLeaves(root.right);int sum=left+right;return sum;}
}

 题目:完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣(LeetCode) 

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

题目分析:

        题目提供的是完全二叉树。那么对于完全二叉树而言。

完全二叉树只有两种情况,情况一:就是满二叉树,情况二:最后一层叶子节点没有满。

对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。

对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来计算。

public class Solution {public int CountNodes(TreeNode root) {if(root==null) return 0;TreeNode left=root.left;//左子树TreeNode right=root.right;int leftDepth=0;//左子树深度int rightDepth=0;while(left!=null){//求出左子树的深度left=left.left;leftDepth++;}while(right!=null){//求出右子树的深度right=right.right;rightDepth++;}if(rightDepth==leftDepth)//左右深度相同,是一个满二叉树{return (int)Math.Pow(2,leftDepth+1)-1;}return CountNodes(root.left)+CountNodes(root.right)+1;}
}

 

对于更详细的解析与其他语言的代码块,可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目:41

http://www.mrgr.cn/news/61842.html

相关文章:

  • Resnet搭建介绍及代码撰写详解(总结6)
  • Excel 单元格小数点精确位数机制
  • 数据结构——(第七章:查找)
  • Nginx 配置基于IP 地址的 Web 服务器
  • 【Axure原型分享】颜色选择器——填充颜色
  • WPF+MVVM案例实战(三)- 动态数字卡片效果实现
  • 【Java】继承
  • 【名单】科大睿智祝贺企业通过DCMM认证最新公示名单
  • 指令集架构(ISA)
  • 教你详细使用Spring框架中编程式事务
  • Vue3 学习笔记(十二)侦听器详解
  • 管家婆财贸ERP BB060.销售订单导入+BB067.销售订单修改BOM类型
  • 期权懂|如何理解Black-Ssholes期权定价模型?
  • 鸿蒙生态的崛起与开发者机遇
  • 3D Gaussian Splatting代码详解(一):模型训练、数据加载
  • C++|运算符优先级
  • Doris集群搭建
  • AI如何提升Web3中的用户体验与数据管理
  • [win] 删除文件空行的方法
  • PPT批量替换字体
  • vue 实现图片预览功能并显示在弹窗的最上方
  • 批发订货系统有哪些功能 b2b网站源码哪里购买靠谱
  • 【测试平台】【前端VUE】工具页面学习记录
  • 当贝Smart1、小明Q3 Pro、大眼橙C1D对比!预算千元,哪款值得买
  • 【C++】RBTree——红黑树
  • vue3 ref和reactive踩坑