/**

  * Definition for a binary tree node.

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     int pathSum(TreeNode* root, int sum) {

         queue<TreeNode*> q;

         int dp[];

         q.push(root);

         int index=;

         int count=;

         while(!q.empty()){

             TreeNode* temp=q.front();

             q.pop();

             q.push(temp->left);

             q.push(temp->right);

             if(temp==NULL) dp[index++]=;

             else dp[index++]=temp->val;

         }

         for(int i=;i<index;i++){

             if(i==&&dp[i]==sum){

                 count++;

             }else if(dp[i]<=&&dp[i]>=-){

                 dp[i]=dp[(i-)/]+dp[i];

                 if(dp[i]==sum) count++;

             }

         }

         return count;

     }

 };

 # Definition for a binary tree node.

 # class TreeNode(object):

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 class Solution(object):

     def pathSum(self,root,sum):

         if root==None:

             return 0

         from collections import defaultdict

         dictionary =defaultdict(int)

         dictionary[0]=1

         pNode,curr_sum,stack,res,prev=root,0,[],0,None

         while(len(stack) or pNode):

             if pNode:

                 curr_sum+=pNode.val

                 stack.append([pNode,curr_sum])

                 dictionary[curr_sum]+=1

                 pNode=pNode.left

             else:

                 pNode,curr_sum=stack[-1]

                 if pNode.right==None or pNode.right==prev:

                     res+=dictionary[curr_sum-sum]

                     if sum==0:

                         res-=1

                     dictionary[curr_sum]-=1

                     stack.pop()

                     prev=pNode

                     pNode=None

                 else:

                     pNode=pNode.right

         return res
     

 /**

  * Definition for a binary tree node.

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     int pathSum(TreeNode* root, int sum) {

         int res=;

         vector<TreeNode*> out;

         dfs(root,sum,,out,res);

         return res;

     }

     //递归先序遍历

     void dfs(TreeNode* node,int sum,int curSum,vector<TreeNode*>& out,int &res){

         if(!node) return;

         curSum+=node->val;

         //cout<<curSum<<endl;

         if(curSum==sum) res++;

         out.push_back(node);

         int t=curSum;

         for(int i=;i<out.size()-;i++){

             t-=out[i]->val;

             if(t==sum) res++;

         }//以当前节点为末节点，利用vector回溯每一个父节点到当前节点的路径和；

         dfs(node->left,sum,curSum,out,res);

         dfs(node->right,sum,curSum,out,res);

         out.pop_back();

     }

 };