Day92 | 靈神 | 二叉樹 路徑總和

112.路徑總和

112. 路徑總和 - 力扣（LeetCode）

思路：

1.遞歸函數意義

如果在根節點為t的樹中可以找到長度為target的路徑就返回true，找不到就返回false

2.參數和返回值

bool tra(TreeNode *t,int target)

參數中的target在傳入之前會先減掉當前結點的值作為給下一個結點傳入的值

如果在根節點為t的樹中可以找到長度為target的路徑就返回true，找不到就返回false

3.終止條件（邊界條件）

如果我們碰到了空節點，那就是false，說明沒找到路徑

if(t==nullptr)return false; 

4.本層邏輯（非邊界條件）

減去本層節點值之后判斷是否是我們要找的路徑

即在葉子結點，并且target也減到0了

然后遞歸遍歷左右子樹，不管哪邊找到了我們都可以返回true

		target-=t->val;if(t->left==nullptr&&t->right==nullptr)return target==0;bool l=tra(t->left,target);bool r=tra(t->right,target);return l||r;	

完整代碼：

class Solution {
public:bool tra(TreeNode *t,int target){if(t==nullptr)return false; target-=t->val;if(t->left==nullptr&&t->right==nullptr)return target==0;bool l=tra(t->left,target);bool r=tra(t->right,target);return l||r;}bool hasPathSum(TreeNode* root, int targetSum) {return tra(root,targetSum);}
};/*
class Solution {
public:bool flag=false;void tra(TreeNode *t,int target){if(t==nullptr)return;target-=t->val;if(t->left==nullptr&&t->right==nullptr&&target==0)flag=true;tra(t->left,target);tra(t->right,target);}bool hasPathSum(TreeNode* root, int targetSum) {tra(root,targetSum);return flag;}
};*/