路径总和
递归法
/** * 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 result = false; void getsum(TreeNode* cur, int targetSum , int sum) { if(cur==nullptr)return; sum += cur->val; //找到叶子节点的和与目标相符 if(cur->left==nullptr && cur->right==nullptr &&sum == targetSum) result = true; getsum(cur->left, targetSum , sum); getsum(cur->right, targetSum , sum); } bool hasPathSum(TreeNode* root, int targetSum) { if(root==nullptr) return false; getsum(root , targetSum , 0); return result; } };
二刷
/** * 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 result = false; void back_trak(TreeNode* cur , int targetSum , int sum) { if(cur == nullptr || result == true) return; if((sum + cur->val) == targetSum && cur->left==nullptr && cur->right==nullptr ) result = true; back_trak(cur->left,targetSum , sum + cur->val ); back_trak(cur->right,targetSum , sum + cur->val ); return; } bool hasPathSum(TreeNode* root, int targetSum) { if(root == nullptr ) return false; back_trak(root , targetSum , 0); return result; } };