https://leetcode.com/problems/path-sum/

递归版

/**
 * 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 == nullptr) {
			return false;
		}
		return pathSum(root, 0, targetSum);
	}

	bool pathSum(TreeNode* node, int sum, int targetSum) {
		sum += node->val;
		if (node->left == nullptr && node->right == nullptr) {
			if (sum == targetSum) {
				return true;
			}
		}
		if (node->left != nullptr) {
			if (pathSum(node->left, sum, targetSum)) {
				return true;
			}
		}
		if (node->right != nullptr) {
			if (pathSum(node->right, sum, targetSum)) {
				return true;
			}
		}
		return false;
	}
};

测试用例

[5,4,8,11,null,13,4,7,2,null,null,null,1]
22
[1,2]
1
[1,2]
0
[1,2,3]
5

简化版

/**
 * 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) {
		return pathSum(root, 0, targetSum);
	}

	bool pathSum(TreeNode* node, int sum, int targetSum) {
		if (node == nullptr) {
			return sum == targetSum;
		}
		sum += node->val;
		return pathSum(node->left, sum, targetSum) || pathSum(node->right, sum, targetSum);
	}
};