1. 題目

給定一個二叉樹，它的每個結點都存放著一個整數值。

找出路徑和等于給定數值的路徑總數。

路徑不需要從根節(jié)點開始，也不需要在葉子節(jié)點結束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）。

二叉樹不超過1000個節(jié)點，且節(jié)點數值范圍是 [-1000000,1000000] 的整數。

示例：root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 810/ \5 -3/ \ \3 2 11/ \ \ 3 -2 1返回 3。和等于 8 的路徑有:1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/path-sum-iii
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權，非商業(yè)轉載請注明出處。

2. 解題

• 以 root 開始求和
• 以 root 的左右子節(jié)點開始求和
  

class Solution {int count = 0; public:int pathSum(TreeNode* root, int sum) {if(root == NULL)return 0;pathSum(root->left,sum);//以root->left節(jié)點從新開始pathSum(root->right,sum);//以root->right節(jié)點從新開始add(root,sum,0);return count;}void add(TreeNode* root, int &sum, int cursum) {if(root == NULL)return;if(cursum+root->val == sum)++count;add(root->left,sum,cursum+root->val);add(root->right,sum,cursum+root->val);} };

總結

以上是生活随笔為你收集整理的LeetCode 437. 路径总和 III（双重递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。