在 Path Sum 和 Path Sum Ⅱ之后,Path Sum 大家庭又迎来了第三位成员。那么这个新成员又提出了什么样的要求呢?
题意是这样的:给出一棵二叉树和一个数值 sum,计算这棵树上的节点之和等于sum 的所有路径的条数。和之前不同的是,这道题中路径可以从树中的任何一个节点开始。
思路:二叉树的题目,大部分都可以用递归的思想来解决,这道题也不例外。基本思路和之前类似,可以参照前面的两篇博文。但是要注意的是,由于路径可以从任何地方开始,在任何地方结束,因此:root 处存在和为 sum 的路径,root->left 处存在和为 sum 的路径以及 root->right 存在和为 sum 的路径这三种情况是需要累加到一起的。我们可以写一个辅助函数int rootSum(TreeNode *root, int sum)
来计算从某个节点 node 处开始和为 sum 的路径条数,那么最后的总条数为 rootSum(root,sum) + pathSum(root->left, sum) + pathSum(root->right, sum)
。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: int rootSum(TreeNode *root, int sum) { if (root == NULL) { return 0; } if (sum == root->val) { return 1 + rootSum(root->left, 0) + rootSum(root->right,0); } else { return rootSum(root->left, sum - root->val) + rootSum(root->right, sum - root->val); } } int pathSum(TreeNode* root, int sum) { if (root == NULL) { return 0; } return rootSum(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); } }; |