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);
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
13
0- 0
已为社区贡献3条内容
所有评论(0)