路徑總和 I ：

給你二叉樹(shù)的根節(jié)點(diǎn) root 和一個(gè)表示目標(biāo)和的整數(shù) targetSum 。判斷該樹(shù)中是否存在 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和 targetSum 。如果存在，返回 true ；否則，返回 false 。

要點(diǎn)：判斷是否存在滿足條件的路徑，只需返回true or false。

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true
解釋：等于目標(biāo)和的根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑如上圖所示。?

解題思路：

每遍歷一個(gè)節(jié)點(diǎn)，就從targetsum中減去當(dāng)前節(jié)點(diǎn)的值，當(dāng)遍歷到葉子節(jié)點(diǎn)時(shí)，如果targetsum=0，說(shuō)明存在該路徑，返回true。反之，返回false

class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if(root==nullptr) return false;targetSum-=root->val;if(root->left==nullptr&&root->right==nullptr){return targetSum==0;}//左子樹(shù)和右子樹(shù)有一個(gè)滿足就可以，所以用||的關(guān)系return hasPathSum(root->left,targetSum)||hasPathSum(root->right,targetSum);}
};

?

路徑總和 II：

給你二叉樹(shù)的根節(jié)點(diǎn) root 和一個(gè)整數(shù)目標(biāo)和 targetSum ，找出所有 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 路徑總和等于給定目標(biāo)和的路徑。

葉子節(jié)點(diǎn) 是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

要點(diǎn)：返回所有滿足題意的路徑，必須是從根節(jié)點(diǎn)開(kāi)始，葉子節(jié)點(diǎn)結(jié)束。

?

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：[[5,4,11,2],[5,8,4,5]]

解題思路：

?添加一個(gè)臨時(shí)數(shù)組，用來(lái)存放當(dāng)前遍歷到的節(jié)點(diǎn)走過(guò)的路徑。其他的與第一題相同，找到符合題意的路徑，就將臨時(shí)數(shù)組存放到結(jié)果數(shù)組中，若不符合條件，需回退，注意回退時(shí)需要將將一個(gè)放到臨時(shí)數(shù)組中的節(jié)點(diǎn)刪掉。

class Solution {
public:vector<vector<int>> res;//所有路徑vector<int> temp;//當(dāng)前路徑void dfs(TreeNode* root, int targetSum){if(root==nullptr) return;temp.push_back(root->val);//當(dāng)前節(jié)點(diǎn)放入到temp中targetSum-=root->val;//從總和中減去//若遇到葉子節(jié)點(diǎn)，需判斷目標(biāo)值是否已經(jīng)為0if(root->left==nullptr&&root->right==nullptr){//目標(biāo)值=0，說(shuō)明當(dāng)前路徑符合題意，temp放到res中if(targetSum==0){res.push_back(temp);}}//遞歸dfs(root->left,targetSum);dfs(root->right,targetSum);//不符合題意，將當(dāng)前節(jié)點(diǎn)從路徑中刪掉temp.pop_back();}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {dfs(root,targetSum);return res;}
};

路徑總和 III:

給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ，和一個(gè)整數(shù) targetSum ，求該二叉樹(shù)里節(jié)點(diǎn)值之和等于 targetSum 的 路徑 的數(shù)目。

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

要點(diǎn)：返回的是所有符合題意的路徑總條數(shù)，與第二題不一樣的是，可以不是從根節(jié)點(diǎn)開(kāi)始，也不需要在葉子節(jié)點(diǎn)結(jié)束。

輸入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
輸出：3
解釋：和等于 8 的路徑有 3 條，如圖所示。?

解題思路：

相當(dāng)于是遞歸套遞歸，構(gòu)建一個(gè)找路徑函數(shù)，遍歷以當(dāng)前節(jié)點(diǎn)為起始的路徑中，是否存在符合題意的路徑，然后再在原函數(shù)遞歸到每一個(gè)節(jié)點(diǎn)，使每一個(gè)節(jié)點(diǎn)都為起始節(jié)點(diǎn)進(jìn)行找符合題意的路徑。

class Solution {
public:int res=0;int pathSum(TreeNode* root, int targetSum) {if(root==nullptr) return res;find_path(root,targetSum);//以當(dāng)前的root節(jié)點(diǎn)為起始節(jié)點(diǎn)，找路徑pathSum(root->left,targetSum);//遞歸當(dāng)前根節(jié)點(diǎn)的左子樹(shù)上的節(jié)點(diǎn)pathSum(root->right,targetSum);//遞歸當(dāng)前根節(jié)點(diǎn)的右子樹(shù)上的節(jié)點(diǎn)return res;}//找路徑函數(shù)void find_path(TreeNode* root,long targetSum){if(root==nullptr) return;targetSum -= root->val;if(targetSum==0)//只要targetsum=0，說(shuō)明存在一條路徑，那么res++{res+=1;}find_path(root->left,targetSum);find_path(root->right,targetSum);}
};