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

代码随想录训练营day18 二叉树

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

//左根右 左右根/*
第一步:如果数组大小为零的话,说明是空节点了。
第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。
第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点
第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)
第五步:切割后序数组,切成后序左数组和后序右数组
第六步:递归处理左区间和右区间*/var hash map[int]int
func buildTree(inorder []int, postorder []int) *TreeNode {hash = make(map[int]int)for i,v := range inorder{ hash[v] = i} root := rebuild(inorder,postorder,len(postorder)-1,0,len(inorder)-1)return root
}func rebuild(inorder []int, postorder []int,rootIdx int,l,r int)*TreeNode{if l>r{return nil }if l ==r {return & TreeNode{Val:inorder[l]}}rootV:= postorder[rootIdx]root:= &TreeNode{Val:rootV}rootIn := hash[rootV]root.Left = rebuild(inorder,postorder,rootIdx-(r-rootIn)-1,l,rootIn-1)root.Right = rebuild(inorder,postorder,rootIdx-1,rootIn+1,r)return root
}

​​​​​​112. 路径总和 

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

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

func hasPathSum(root *TreeNode,targetSum int) bool{if root ==nil { return false}if root.Left == nil && root.Right ==nil{return root.Val == targetSum}return hasPathSum(root.Left,targetSum-root.Val) || hasPathSum(root.Right,targetSum-root.Val) 
}

 

513. 找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 var depth intvar res int
func findBottomLeftValue(root *TreeNode) int {depth,res = 0,0 dfs(root,1)return res
}func dfs(root *TreeNode ,d int){if root ==nil{ return }if root.Left ==nil && root.Right == nil &&depth <d{//当前深度大于之前收录的深度depth = dres = root.Val}dfs(root.Left,d+1)dfs(root.Right,d+1)
}

http://www.lryc.cn/news/120375.html

相关文章:

  • 图像的平移变换之c++实现(qt + 不调包)
  • 云原生K8S------Yaml文件详解
  • 测试开发环境安装
  • 微信小程序如何引入Iconfont
  • php使用get和post传递数据出现414 Request-URI Too Large的解决方案
  • 复现大华智慧园区综合管理平台SQL注入漏洞
  • 【uniapp】uniapp设置安全区域:
  • Grafana技术文档--基本安装-docker安装并挂载数据卷-《十分钟搭建》-附带监控服务器
  • 24大连交通大学软件工程813题库
  • 数据治理-组织变革
  • html的语义化
  • 8/12 题解
  • 九耶丨阁瑞钛伦特-产品经理面试题
  • 前后端分离项目接口权限检查方案
  • 步入React正殿 - 事件处理
  • NLP(六十四)使用FastChat计算LLaMA-2模型的token长度
  • 个保新标 | 《信息安全技术 敏感个人信息处理安全要求》(征求意见稿)发布
  • 【uniapp 返回顶部】
  • 无代码集成励销云CRM连接更多应用
  • QT自带PDF库的使用
  • SQL | 排序检索的数据
  • 8. yaml文件管理
  • Cobbler自定义yum源
  • 《算法竞赛·快冲300题》每日一题:“特殊数字”
  • 在R中比较两个矩阵是否相等
  • 商城-学习整理-基础-商品服务API-属性分组(七)
  • 什么是响应式设计?列举几种实现响应式设计的方法。
  • Java类和对象(一文读懂)
  • 用友移动管理系统 任意文件上传漏洞复现(HW0day)
  • 启动springboot,出现Unable to start embedded Tomcat