LeetCode Path Sum III You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000. Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

---

问二叉树中有多少条路径和等于sum的路径，这里的路径不一定要起于根节点，也不一定要终于叶子结点，但是必须从从上往下（从父亲到孩子）。 我一开始的解法是，对每个节点，保留从其所有父亲节点到该节点的路径和，每个节点都统计到当前节点的路径和等于sum的路径数。 代码如下： [cpp] class Solution { private: void dfs(TreeNode* root, vector<int> all, int target, int& ans) { vector<int> newAll = { root->val }; for (int i = 0; i < all.size(); ++i)newAll.push_back(root->val + all[i]); for (int i = 0; i < newAll.size(); ++i) { if (newAll[i] == target)++ans; } if (root->left)dfs(root->left, newAll, target, ans); if (root->right)dfs(root->right, newAll, target, ans); } public: int pathSum(TreeNode* root, int sum) { if (root == NULL)return 0; int ans = 0; dfs(root, {}, sum, ans); return ans; } }; [/cpp] 本代码提交AC，用时62MS。这种解法需要保存所有的路径和，且有vector的复制，效率较低。 我这种解法是以每个节点作为终点统计一下路径和，网上有另一种解法，以每个节点作为开始节点，统计以这个点开始的所有路径和是否等于sum，然后递归的在其子树进行统计。 对于每个节点，走到其孩子节点时，对应的sum需要更新。代码如下： [cpp] class Solution { private: int dfs(TreeNode* root, int sum) { if (root == NULL)return 0; int ans = 0; if (root->val == sum)++ans; ans += dfs(root->left, sum – root->val); ans += dfs(root->right, sum – root->val); return ans; } public: int pathSum(TreeNode* root, int sum) { if (root == NULL)return 0; return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); } }; [/cpp] 本代码提交AC，用时32MS，效率更高。]]>