LeetCode112 路径总和

前言

题目： 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, vector<int>& path, vector<int>& 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) {vector<int> path;vector<int> 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);}
};