Path Sum

原題鏈接Path Sum

判斷二叉樹中有沒有一條從根節點到葉子節點的路徑元素和為給定值

只需要遍歷所有路徑即可，需要注意的是對葉子節點的判斷，需要滿足左右兩個節點都是空的條件時才為葉子節點

代碼如下

/*** 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) {return root && findPathSum(root, sum); } private:bool findPathSum(TreeNode* root, int sum){if(!root) return false;sum -= root->val;/* 是葉子節點同時到達該葉子節點時，剩余和為0 */if(!root->left && !root->right && !sum) return true;return findPathSum(root->left, sum) || findPathSum(root->right, sum);} };

---

Path Sum II

原題鏈接Path Sum II

返回所有路徑上的元素值，路徑要求仍然是總和為給定值

只需要將返回true和false改為記錄路徑值即可

代碼如下

/*** 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:vector<vector<int>> pathSum(TreeNode* root, int sum) {vector<vector<int>> res;vector<int> cur;findPathSum(root, sum, cur, res);return res;} private:void findPathSum(TreeNode* root, int sum, vector<int>& cur, vector<vector<int>>& res){if(!root) return;sum -= root->val;cur.emplace_back(root->val);if(!root->left && !root->right && !sum){res.emplace_back(cur);}else{findPathSum(root->left, sum, cur, res);findPathSum(root->right, sum, cur, res);}cur.pop_back();} };

---

這兩道題同樣是利用遞歸，思路比較簡單

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----找到二叉树所有和为给定值的路径的全部內容，希望文章能夠幫你解決所遇到的問題。

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