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 and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which
sum is 22.
比较基础的题，3月做PAT的时候正好还有这道题，题目说的是二叉树，没有说是二叉排序数，
基本代码如下：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root,int sum)
{
if (!root)
return false;
if(!root->left&&!root->right)
return sum==root->val;
int exp=sum-root->val;
return hasPathSum(root->left,exp)||hasPathSum(root->right,exp);
}
};
从代码中可以看到无论当前exp是什么情况我们都必须要向左和向右检查。
如果是二叉排序数的话我们是可以做一些剪枝来增加效率的，具体怎么剪枝大家可以思考一下~