408数据结构真题2014-41

题目

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

注：链接题目仅代表和本题大体相似
因为是考研笔试，本题代码以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);
}

这篇好文章是转载于：学新通技术网