题解 | #牛群特殊路径的数量#
牛群特殊路径的数量
https://www.nowcoder.com/practice/1c0f95d8396a432db07945d8fe51a4f5
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ // 寻找以根节点为出发点的路径的数目 int inordered(TreeNode* root, int sum) { // 到了叶子结点 int total = 0; if (root == nullptr) return 0; if (root->val == sum) { total++; } // 因为是计算从根节点出发的,所以遍历左右子树时,都得减去根节点的值,比如如果刚好root的值和sum相等,在去遍历左右子树时,应该就是判断是否有路径和为0的情况,那么这个sum值随着路径减下去,当减到某个值和sum相等时,则表示该路径同样满足和为sum。 total += inordered(root->left, sum-root->val); total += inordered(root->right, sum-root->val); return total; } int pathSum(TreeNode* root, int sum) { // write code here if (root == nullptr) return 0; int res = inordered(root, sum); res += pathSum(root->left, sum); res += pathSum(root->right, sum); return res; } };