408数据结构真题2014-41

• 题目
• AC代码

本题链接：AcWing 3766. 二叉树的带权路径长度

注：链接题目仅代表和本题大体相似
因为是考研笔试，本题代码以C语言去写

代码解释：本题要求的是带权路径的长度之和，带权路径的长度 = 权值点 * 该点到根节点的距离，下面举一个栗子去说明这一点：

比如栗子中给的这棵树，带权路径的长度之和 = (12 * 1 + 2 * 1 + 6 * 2 + 4 * 2) = 34
题目中要求的是所有叶节点的带权路径之和，故不包含2这个点，答案为：(12 * 1 + 6 * 2 + 4 * 2) = 32，不难看出，本题其实是要求我们遍历这棵树，我们遍历树的方法可以采用dfs和bfs两种方法，笔试建议采用dfs的写法，dfs写起来要比bfs精简很多！

代码：

 
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);
}