题目描述
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree andsum = 22,
return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.
题目大意
给定一个二叉树和一个sum值，看看是否有一条从根到叶子结点的路径，使得这条路径上各个结点的值相加刚好等于sum。
思路
递归思路求解，递归每条路径，看是否有一条路径之和刚好等于sum。
递归出口是：
（1）返回为true：当前结点刚好是叶子结点&&sum-当前结点的值为0。
（2）返回为false：root == NULL。
避坑：sum和各个结点值有可能是负数；
代码
#include<iostream>
using namespace std;
// Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
typedef TreeNode* tree;
bool hasPathSum(TreeNode *root, int sum)
{
if(root == NULL)return false;
// 保证该店是叶子结点且加到这儿的和为sum
if(root->val==sum && root->left==NULL && root->right==NULL)
return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
int main()
{
tree t = new TreeNode(-2);
t->left = new TreeNode(-3);
cout<<hasPathSum(t, -5)<<endl;
//cout<<-5-(-2)<<endl;
return 0;
}
以上。
