Path Sum

常规做法是算出每一条路径的和然后和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     }

View Code

网上看到别人的写法清晰简洁，参考一下：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 };

View Code