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.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
/ \
/ / \
/ \ \
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
方法一：利用深度优先搜索DFS的方法来遍历每一条完整的路径，利用递归方法不停地找子节点的左右结点。首先，若输入的是空节点，则返回false，若是为叶子结点且其值为当下的值时，则返回true,否则，只要子节点的左右结点中任一结点可行则返回true。(C++)
bool hasPathSum(TreeNode* root, int sum) {
if(!root)
return false;
if(root->val==sum&&!root->left&&!root->right)
return true;
return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);
}
方法二：使用遍历的方法，每一个结点都加上其父结点的值，如果到叶子结点时，其值等于sum，就存在一条符合题意的路径，在这道题中，不一定非要右结点先入栈，左右顺序不影响结果。（C++）
bool hasPathSum(TreeNode* root, int sum) {
if(!root)
return false;
stack<TreeNode*> s{{root}};
while(!s.empty()){
TreeNode* tmp=s.top();
s.pop();
if(!tmp->left&&!tmp->right){
if(tmp->val==sum)
return true;
}
if(tmp->right){
tmp->right->val+=tmp->val;
s.push(tmp->right);
}
if(tmp->left){
tmp->left->val+=tmp->val;
s.push(tmp->left);
}
}
return false;
}