112. 路徑總和

題目

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。

說明: 葉子節點是指沒有子節點的節點。

示例:
給定如下二叉樹，以及目標和 sum = 22，
在這里插入圖片描述
返回 true, 因為存在目標和為 22 的根節點到葉子節點的路徑 5->4->11->2。

遞歸解

1、函數參數：當前樹的根結點、當前累積的路徑和，目標路徑和；返回值為空
2、終止條件：該結點為空
3、單層邏輯：如果該結點不為空，則在累積路徑和上加上該結點的值。如果該結點是葉子結點，判斷此時的累積路徑和與目標路徑和是否相同，如果相同則將全局變量ifHas改為true，認為能夠找到路徑和為目標值的路徑。然后返回父結點，回溯到上一個狀態，參數會自動更正為上一個狀態的參數。接下來就是按順序對該結點的左右孩子進行遍歷

這個思路是有問題的，因為它只在葉子結點之后才回溯，這是不合理的，但是也能AC。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool ifHas=false;void traversal(TreeNode* cur,int target,int Mysum){if(cur==NULL)  return;if(cur!=NULL)  Mysum+=cur->val;//如果是葉子結點，則進行比較if(cur->left==NULL && cur->right==NULL){//如果和目標結果相同if(Mysum == target) ifHas=true;return;}if(cur->left){traversal(cur->left,target,Mysum);}if(cur->right){traversal(cur->right,target,Mysum);}return ;}bool hasPathSum(TreeNode* root, int sum) {//if(root == NULL) return false;int Mysum=0;traversal(root,sum,Mysum);return ifHas;}
};

在這里插入圖片描述

遞歸解，其他人的解法

1、函數參數、返回值確定
之前有個結論：如果需要搜索整棵二叉樹，那么遞歸函數就不要返回值，如果要搜索其中一條符合條件的路徑，遞歸函數就需要返回值，因為遇到符合條件的路徑就要及時返回。
本題并不需要遍歷整棵樹，所以遞歸函數需要返回值，可以用bool類型表示。

bool traversal(TreeNode* cur,int count)

2、終止條件確定
在如何統計一條路徑和的方法上，代碼隨想錄使用遞減的方法，讓計數器count初始為目標和，然后每次減去遍歷路徑結點上的數值。如果最后count==0，同時到了葉子結點的話，說明了找到目標和。如果遍歷到了葉子結點，cout不為0，就是沒找到

if(!cur->left && !cur->right && count == 0) return true;		//遇到葉子結點，并且計數為0
if(!cur->left && !cur->right) return false;					//遇到葉子結點，沒有找到合適的邊，直接返回

3、確定單層遞歸的邏輯
因為終止條件是判斷也自己誒單，所以遞歸過程中就不要讓空結點進入遞歸了。
遞歸函數的返回值為true的話說明了找到了合適的路徑，應該立刻返回

if(cur->left)
{count -=cur->left->val;//遇到葉子結點返回true，則直接返回true；if(traversal(cur->left,count)) return true;count +=cur->left->val;			//回溯，撤銷處理結果
}
if(cur->right)
{count -=cur->right->val;//遇到葉子結點返回true，則直接返回true；if(traversal(cur->right,count)) return true;count +=cur->right->val;			//回溯，撤銷處理結果
}
return false;

class Solution {
public:bool traversal(TreeNode* cur,int count)		{if(!cur->left && !cur->right && count == 0) return true;		//遇到葉子結點，并且計數為0if(!cur->left && !cur->right) return false;					//遇到葉子結點，沒有找到合適的邊，直接返回if(cur->left){count -=cur->left->val;//遇到葉子結點返回true，則直接返回true；if(traversal(cur->left,count)) return true;count +=cur->left->val;			//回溯，撤銷處理結果}if(cur->right){count -=cur->right->val;//遇到葉子結點返回true，則直接返回true；if(traversal(cur->right,count)) return true;count +=cur->right->val;			//回溯，撤銷處理結果}return false;}bool hasPathSum(TreeNode* root, int sum) {if(root == NULL) return false;return traversal(root,sum-root->val);}
};

迭代解，其他人的解法

如果使用棧模擬遞歸的話對于回溯如何處理？
此時棧里面的一個元素不僅要記錄該結點指針，還要記錄從頭結點到該結點的路徑數值總和。
這里使用pair結構來存放棧里面的元素。（第一次用這個結構）
定義為：

pair<TreeNode*,int> pair<結點指針，路徑數值>

為棧中的一個元素。
使用棧模擬前序遍歷;

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int sum) {if(root == NULL) return false;//此時棧里面要放的是pair<結點指針，路徑數值>stack<pair<TreeNode*,int>> st;st.push(pair<TreeNode*,int>(root,root->val));while(!st.empty()){pair<TreeNode*,int> node = st.top();st.pop();//如果這個結點是葉子結點，同時該結點的路徑數值等于sum，那么就返回trueif(!node.first->left &&!node.first->right && sum == node.second ) return true;//右結點，壓進去一個結點的時候，將該結點的路徑數值也記錄下來if(node.first->right){st.push(pair<TreeNode*,int>(node.first->right,node.second+node.first->right->val));}//右結點，壓進去一個結點的時候，將該結點的路徑數值也記錄下來if(node.first->left){st.push(pair<TreeNode*,int>(node.first->left,node.second+node.first->left->val));}}return false;}
};

113. 路徑總和 II

題目

給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等于給定目標和的路徑。

說明: 葉子節點是指沒有子節點的節點。
在這里插入圖片描述

遞歸解

同樣的道理，Mysum作為函數參數每次返回的時候會自動更正，不需要手動回溯。
完成一次子結果，就將子結果送入paths中。
path需要手動回溯。

 path.push_back(cur->left->val);traversal(cur->left,target,Mysum);path.pop_back();

同時需要注意，在一開始要將根結點送入path中，因為在我們的遞歸函數中只對左右孩子進行push_back()

class Solution {
public:vector<vector<int>> paths;vector<int> path;void traversal(TreeNode* cur,int target,int Mysum){if(cur==NULL)  return;if(cur!=NULL){Mysum+=cur->val;}  //如果是葉子結點，則進行比較if(cur->left==NULL && cur->right==NULL){//如果和目標結果相同if(Mysum == target){paths.push_back(path);}return;}if(cur->left){path.push_back(cur->left->val);traversal(cur->left,target,Mysum);path.pop_back();}if(cur->right){path.push_back(cur->right->val);traversal(cur->right,target,Mysum);path.pop_back();}return ;}vector<vector<int>> pathSum(TreeNode* root, int sum) {if(root==NULL) return {};int Mysum=0;path.push_back(root->val);traversal(root,sum,Mysum);return paths;}
};

遞歸解，參考別人的思路

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:vector<vector<int>> paths;vector<int> path;//遞歸函數不需要返回值，因為我們要遍歷整個樹void traversal(TreeNode* cur,int count){if(!cur->left && !cur->right && count == 0)     //遇到了葉子結點且找到了和為sum的路徑{paths.push_back(path);return;}if(!cur->left && !cur->right ) return;if(cur->left){path.push_back(cur->left->val);count-=cur->left->val;traversal(cur->left,count);count+=cur->left->val;path.pop_back();}if(cur->right){path.push_back(cur->right->val);count-=cur->right->val;traversal(cur->right,count);count+=cur->right->val;path.pop_back();}return;}
public:vector<vector<int>> pathSum(TreeNode* root, int sum) {paths.clear();path.clear();if(root==NULL) return paths;path.push_back(root->val);traversal(root,sum-root->val);return paths;}
};