【Leetcode学习笔记】路径总和

本文主要是介绍【Leetcode学习笔记】路径总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
在这里插入图片描述
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

本题难度标记为简单，但是递归思想总是让我头疼，每次都要调试看到一步步的过程才清晰明了。

ACM模式代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <stack>using namespace std;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 backtracking(TreeNode* root, int target){if(root->left == nullptr && root->right == nullptr && target == 0){return true;}if(root->left == nullptr && root->right == nullptr && target != 0){return false;}if(root->left != nullptr){if(backtracking(root->left, target-root->left->val) == true){return true;}}if(root->right != nullptr){if(backtracking(root->right, target-root->right->val) == true){return true;}       }return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == nullptr) return false;return backtracking(root, targetSum-root->val);}
};int main() {TreeNode* root = new TreeNode(5);TreeNode* node1 = new TreeNode(4);TreeNode* node2 = new TreeNode(8);TreeNode* node3 = new TreeNode(11);TreeNode* node4 = new TreeNode(13);TreeNode* node5 = new TreeNode(4);TreeNode* node6 = new TreeNode(7);TreeNode* node7 = new TreeNode(2);TreeNode* node8 = new TreeNode(1);root->left = node1;root->right = node2;node1->left = node3;node2->left = node4;node2->right = node5;node3->left = node6;node3->right = node7;node5->right = node1;Solution solution;bool result = solution.hasPathSum(root, 22);std::cout << "Has path sum 22: " << (result ? "true" : "false") << std::endl;// Clean updelete root->left->left->left;delete root->left->left->right;delete root->left->left;delete root->left;delete root->right->right->right;delete root->right->right;delete root->right->left;delete root->right;delete root;return 0;
}