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 1return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
s思路： 1. 遍历。每次减，如果到leaf，结果为０,则说明有这样的path存在。要一条path一条的试，所以用recursive的方式，dfs。 2. 如何用iterative呢？具体说，如何用iterative来实现PRe-order？先stack中一路向左保存所有根节点，然后取出头上的根节点作为cur指针，可以肯定的是cur指针没有左孩子，先判断是否有右孩子，没有右孩子则可以弹出stack顶上指针；有右孩子，则把cur=cur->right。这里需要区别和in-order不同的地方：在in-order中，cur取出之后，直接弹出，所以不需要用pre来存之前访问过的地方，而在pre-order中，有右孩子，则不能弹出stack的指针，因为计算path sum时还需要这个指针对应的值。为了防止重复访问，比如：当右孩子访问之后，又重新回到这个节点，此时如果判断是否有右孩子的话，就会重复访问右孩子。为了避免重复，可以在用一个pre指针，每次在访问节点后，把pre=cur，然后判断一次cur->right!=pre,即可避免！
//方法１：recursive.仔细分辨，是pre-order:先访问中间，然后左边，最后右边。class Solution {public: bool haspathSum(TreeNode* root, int sum) { if(!root) return false; if(!root->left&&!root->right) return root->val==sum; if(hasPathSum(root->left,sum-root->val)) return true; return hasPathSum(root->right,sum-root->val); }};//方法２：iterative:stack实现。class Solution {public: bool hasPathSum(TreeNode* root, int sum) { stack<TreeNode*> ss; int path=0; TreeNode* cur=root, *pre=NULL; while(cur||!ss.empty()){ while(cur){//先‘中’，‘左’ path+=cur->val; ss.push(cur); cur=cur->left; } cur=ss.top(); if(!cur->left&&!cur->right&&path==sum) return true; if(cur->right&&cur->right!=pre){//后‘右’ cur=cur->right; }else{ pre=cur; ss.pop();//当cur没有右孩子或者右孩子已经访问，才能弹出cur //这和in-order的处理方式就不同，在in-order中，cur取出之后，直接弹出，所以不需要用pre来存之前访问过的地方！ path-=cur->val; cur=NULL; } } return false; }};新闻热点
疑难解答
