408数据结构真题2014-41
题目
注:链接题目仅代表和本题大体相似
因为是考研笔试,本题代码以C语言去写
AC代码
代码解释:本题要求的是带权路径的长度之和,带权路径的长度 = 权值点 * 该点到根节点的距离,下面举一个栗子去说明这一点:
比如栗子中给的这棵树,带权路径的长度之和 = (12 * 1 2 * 1 6 * 2 4 * 2) = 34
题目中要求的是所有叶节点的带权路径之和,故不包含2
这个点,答案为:(12 * 1 6 * 2 4 * 2) = 32
,不难看出,本题其实是要求我们遍历这棵树,我们遍历树的方法可以采用dfs
和bfs
两种方法,笔试建议采用dfs
的写法,dfs写起来要比bfs精简很多!
代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int dfs(struct TreeNode* root, int depth){
if (!root) return 0;
if (!root -> left && !root -> right)
return root -> val * depth;
else return dfs(root -> left, depth 1) dfs(root -> right, depth 1);
}
int pathSum(struct TreeNode* root) {
return dfs(root, 0);
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfeeac
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01