112 路径总和
https://leetcode.cn/problems/path-sum/description/
做法:递归
本做法中的targetSum为剔除掉当前节点剩余的targetSum,即左/右节点到达子节点需要走的路径和
思路版
该版本没有怎么简化,着重于详细的思路
/**
* 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 {
private:
bool dfs(TreeNode* root, int targetSum){
// 判断是否存在左节点
if(root->left){
// 如果左节点存在满足条件的路径,那么当前节点也存在满足条件的路径
if(dfs(root->left, targetSum - root->left->val))
return true;
}
// 右节点同理
if(root->right){
if(dfs(root->right, targetSum - root->right->val))
return true;
}
// 如果当前节点为叶子节点
if(!root->left && !root->right){
if(targetSum == 0)
return true;
else
return false;
}
return false;
}
public:
bool hasPathSum(TreeNode* root, int targetSum) {
// 如果根节点没空,不存在题解
if(!root)
return false;
return dfs(root, targetSum - root->val);
}
};
或写成
class Solution {
private:
bool traversal(TreeNode* cur, int count) {
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点,并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
if (cur->left) { // 左
count -= cur->left->val; // 递归,处理节点;
if (traversal(cur->left, count)) return true;
count += cur->left->val; // 回溯,撤销处理结果
}
if (cur->right) { // 右
count -= cur->right->val; // 递归,处理节点;
if (traversal(cur->right, count)) return true;
count += cur->right->val; // 回溯,撤销处理结果
}
return false;
}
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
return traversal(root, sum - root->val);
}
};
简化版
/**
* 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 hasPathSum(TreeNode* root, int targetSum) {
if(root == NULL) return false;
if(!root->left && !root->right && targetSum == root->val) return true;
return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}
};