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,5/ \4 8/ / \11 13 4/ \\7 21
return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.
程序代码如下：
#include<iostream>#include<queue>#include<vector>using namespace std;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==NULL)return false;//类似先序遍历，首先访问根节点treeNodeVec.push_back(root);//判断是否到路径终点if(root->left==NULL && root->right==NULL){int tempSum=0;for(vector<TreeNode*>::iterator iter=treeNodeVec.begin();iter!=treeNodeVec.end();++iter){tempSum+=(*iter)->val;}if(sum==tempSum)return true;else{treeNodeVec.pop_back();//叶子节点回溯操作return false;}}bool lflag=false,rflag=false; //递归判断左右子树是否为true//如果存在左子树则判断，否则为falseif(root->left!=NULL)lflag=hasPathSum(root->left,sum);if(!lflag && root->right!=NULL) //如果左子树为true，则停止判断右子树rflag=hasPathSum(root->right,sum);treeNodeVec.pop_back(); //非叶节点回溯，，最后vec为空return lflag || rflag;}public:vector<TreeNode*> treeNodeVec;};int main(){TreeNode node1(1);TreeNode node2(2);node1.left=&node2;Solution solution;cout<<solution.hasPathSum(&node1,0)<<endl;return 0;}
天才是百分之一的灵感加上百分之久十久的努力
