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