正文
leetcode 437 Path Sum III 路径和
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
相关问题：112 path sum
/**
* 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;
}
};
想使用层序遍历+动态规划的方法O(n)完成，被NULL节点不能加入queue<TreeNode*> q给卡住了，之后再看看怎么改；对这种含有NULL多的怎么层序啊啊啊啊啊啊；
先看看大佬的方法：
python：非递归先序遍历+字典
# 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
网上看的别人的C++代码：
原理：递归先序遍历，遍历的时候用vector记录根节点到每一个节点的路径，然后计算每一个父节点到当前节点的路径和，并判断与sum的值是否相等：
/**
* 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();
}
};
