相关问题：112 path sum

 

 

1 /** 2  * Definition for a binary tree node. 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     int pathSum(TreeNode* root, int sum) {13         queue
     
       q;14         int dp[1000];15         q.push(root);16         int index=0;17         int count=0;18         while(!q.empty()){19             TreeNode* temp=q.front();20             q.pop();21             q.push(temp->left);22             q.push(temp->right);23             if(temp==NULL) dp[index++]=1000010;24             else dp[index++]=temp->val;25         }26         for(int i=0;i
      
       =-1000000){30                 dp[i]=dp[(i-1)/2]+dp[i];31                 if(dp[i]==sum) count++;32             }33         }34         return count;35     }36 };
      
     

想使用层序遍历+动态规划的方法O(n)完成，被NULL节点不能加入queue<TreeNode*>  q给卡住了，之后再看看怎么改；对这种含有NULL多的怎么层序啊啊啊啊啊啊；

 

 

先看看大佬的方法：

python：非递归先序遍历+字典

1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.left = None 6 #         self.right = None 7  8 class Solution(object): 9     def pathSum(self,root,sum):10         if root==None:11             return 012         from collections import defaultdict13         dictionary =defaultdict(int)14         dictionary[0]=115         pNode,curr_sum,stack,res,prev=root,0,[],0,None16         while(len(stack) or pNode):17             if pNode:18                 curr_sum+=pNode.val19                 stack.append([pNode,curr_sum])20                 dictionary[curr_sum]+=121                 pNode=pNode.left22             else:23                 pNode,curr_sum=stack[-1]24                 if pNode.right==None or pNode.right==prev:25                     res+=dictionary[curr_sum-sum]26                     if sum==0:27                         res-=128                     dictionary[curr_sum]-=129                     stack.pop()30                     prev=pNode31                     pNode=None32                 else:33                     pNode=pNode.right34         return res35

 网上看的别人的C++代码：

原理：递归先序遍历，遍历的时候用vector记录根节点到每一个节点的路径，然后计算每一个父节点到当前节点的路径和，并判断与sum的值是否相等：

1 /** 2  * Definition for a binary tree node. 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     int pathSum(TreeNode* root, int sum) {13         int res=0;14         vector
     
       out;15         dfs(root,sum,0,out,res);16         return res;17     }18     //递归先序遍历19     void dfs(TreeNode* node,int sum,int curSum,vector
      
       & out,int &res){20         if(!node) return;21         curSum+=node->val;22         //cout<
       
        <
        
         val;28             if(t==sum) res++;29         }//以当前节点为末节点，利用vector回溯每一个父节点到当前节点的路径和；30         dfs(node->left,sum,curSum,out,res);31         dfs(node->right,sum,curSum,out,res);32         out.pop_back();33     }34 };