网站建设如何财务处理,wordpress第三方订阅地址,网站备案 换空间,网页开发需要学什么技术前言 题目#xff1a; 112. 路径总和 文档#xff1a; 代码随想录——路径总和 编程语言#xff1a; C 解题状态#xff1a; 成功解答#xff01; 思路
比较简单的一个思路是遍历所有的路径#xff0c;求和后再查找目标值。但是#xff0c;最好的方法是一边遍历#x…前言 题目 112. 路径总和 文档 代码随想录——路径总和 编程语言 C 解题状态 成功解答 思路
比较简单的一个思路是遍历所有的路径求和后再查找目标值。但是最好的方法是一边遍历一边比对。
代码
方法一遍历后再查找
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void findPath(TreeNode* node, vectorint path, vectorint res) {path.push_back(node - val);if (node - left NULL node - right NULL) {int sum 0;for (int i 0; i path.size(); i) {sum path[i];}res.push_back(sum);}if (node - left) {findPath(node - left, path, res);path.pop_back();}if (node - right) {findPath(node - right, path, res);path.pop_back();}}bool hasPathSum(TreeNode* root, int targetSum) {vectorint path;vectorint result;if (root NULL) return false;findPath(root, path, result);for (int i 0; i result.size(); i) {if (result[i] targetSum) {return true;}}return false;}
};方法二边遍历边查找
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool findPath(TreeNode* node, int count) {if (!node - left !node - right count 0) return true;if (!node - left !node - right) return false;if (node - left) {count - node - left - val;if (findPath(node - left, count)) return true;count node - left - val;}if (node - right) {count - node - right - val;if (findPath(node - right, count)) return true;count node - right - val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if (root NULL) return false;return findPath(root, targetSum - root - val);}
};
