常规做法是算出每一条路径的和然后和sum比较。类似的题目是打印出从根节点到每个叶子节点的路径。
之前学过分支界限法，刚开始觉得可以用来解这道题，不过再想想的话觉得应该不行，分支界限法是找最优化的。
常规的做法中加上一些小的判别，会付出一些代价，不过也许会比盲目相加好一些吧。比如说每到一个结点sum就减去那个结点的值，如果结果小于0就不走这条路了。
不过问题是题目上并没有说结点的值都是正值呀，所以这样不行。
二叉树的非递归遍历参看：http://blog.csdn.net/kofsky/article/details/2886453
/*
http://www.cppblog.com/CodeStream/archive/2011/03/25/142700.html
STL
栈
基本操作：
push(x) 将x加入栈中，即入栈操作
pop() 出栈操作(删除栈顶)，只是出栈，没有返回值
top()
返回第一个元素(栈顶元素)
size() 返回栈中的元素个数
empty() 当栈为空时，返回 true
*/
虽然这么想的，但是代码现在还是不会写。
才写了这么多就不知道怎么写了，太惭愧了
1 bool hasPathSum(TreeNode *root, int sum) { 2 if(!root) 3 return false; 4 int s; 5 stack(TreeNode *) S; 6 S.push(root); 7 s+=root->value; 8 if(root->left) 9 { 10 S.push(root->left); 11 s+=root->left->value; 12 } 13 14 }
网上看到别人的写法清晰简洁，参考一下：http://blog.csdn.net/tingmei/article/details/8086220
他的写法和二叉树的先序遍历很像，和求二叉树的深度也很像。
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 bool hasPathSum(TreeNode *root, int sum) { 13 if(!root) 14 return false; 15 sum-=root->val; 16 if(sum==0&&!root->left&&!root->right) 17 return true; 18 bool left=hasPathSum(root->left,sum); 19 bool right=hasPathSum(root->right,sum); 20 return left||right; 21 } 22 };
原文：http://www.cnblogs.com/crane-practice/p/3590615.html
