【数据结构】算法 层数最深叶子节点的和 Deepest Leaves Sum
2021/10/19 1:09:21
本文主要是介绍【数据结构】算法 层数最深叶子节点的和 Deepest Leaves Sum,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 层数最深叶子节点的和 Deepest Leaves Sum
- 思路
- Tag
层数最深叶子节点的和 Deepest Leaves Sum
一棵二叉树的根节点root
,返回层数最深的叶子节点的和。
in: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] out:15
思路
对树的处理基本就是 DFS,BFS。
看到一个非常有意思的思路,通过dfs递归求解,递归方法中需要有一个当前节点node,和当前节点node的深度。同样在外部我们还要有一个max_deep来记录最深的层数,以及一个记录结果的ans。
每次进入递归方法时,除了边界条件外,还要将节点的层数与最大的深度进行比较如果当前的节点深度比记录的max还要大,说明我们已经找到了一个更深的节点,将之前的max_deep更新,并将当前的节点值保存到ans。如果我们遇到的节点与当前记录的最大深度一致,那么就加入ans。
时间复杂度O(n) n是节点数。空间复杂度O(H)即树深度,当然最差情况下也是O(n)
int max_deep,ans; public void getResult(TreeNode root ,int k ){ if(root==null){ return ; } if(k == max_deep){ ans += root.val;//找到同样深度的node,val相加 } if(k>max_deep){ max_k = k; ans = root.val;//找到更深的node,val覆盖 } getResult(root.left,k+1); getResult(root.right,k+1); return; } public int deepestLeavesSum(TreeNode root) { getResult(root,0); return ans; }
Tag
Tree
,DFS
这篇关于【数据结构】算法 层数最深叶子节点的和 Deepest Leaves Sum的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求