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，結(jié)果為０,則說明有這樣的path存在。要一條path一條的試，所以用recursive的方式，dfs。 2. 如何用iterative呢？具體說，如何用iterative來實現(xiàn)PRe-order？先stack中一路向左保存所有根節(jié)點，然后取出頭上的根節(jié)點作為cur指針，可以肯定的是cur指針沒有左孩子，先判斷是否有右孩子，沒有右孩子則可以彈出stack頂上指針；有右孩子，則把cur=cur->right。這里需要區(qū)別和in-order不同的地方：在in-order中，cur取出之后，直接彈出，所以不需要用pre來存之前訪問過的地方，而在pre-order中，有右孩子，則不能彈出stack的指針，因為計算path sum時還需要這個指針對應的值。為了防止重復訪問，比如：當右孩子訪問之后，又重新回到這個節(jié)點，此時如果判斷是否有右孩子的話，就會重復訪問右孩子。為了避免重復，可以在用一個pre指針，每次在訪問節(jié)點后，把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實現(xiàn)。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沒有右孩子或者右孩子已經(jīng)訪問，才能彈出cur //這和in-order的處理方式就不同，在in-order中，cur取出之后，直接彈出，所以不需要用pre來存之前訪問過的地方！ path-=cur->val; cur=NULL; } } return false; }};新聞熱點
疑難解答
