LeetCode -- Path Sum III分析及实现方法
LeetCode--PathSumIII分析及实现方法
题目描述：
Youaregivenabinarytreeinwhicheachnodecontainsanintegervalue. Findthenumberofpathsthatsumtoagivenvalue. Thepathdoesnotneedtostartorendattherootoraleaf,butitmustgodownwards(travelingonlyfromparentnodestochildnodes). Thetreehasnomorethan1,000nodesandthevaluesareintherange-1,000,000to1,000,000.
给定一个二叉树，遍历过程中收集所有可能路径的和，找出和等于X的路径树。
思路：
设当前节点为root,分别收集左右节点路径和的集合，merge到当前集合中；
将当前节点添加到数组中，构成新的可能路径。
实现代码：
/**
*Definitionforabinarytreenode.
*publicclassTreeNode{
*publicintval;
*publicTreeNodeleft;
*publicTreeNoderight;
*publicTreeNode(intx){val=x;}
*}
*/
publicclassSolution{
privateint_sum;
privateint_count;
publicintPathSum(TreeNoderoot,intsum)
{
_count=0;
_sum=sum;
Travel(root,newList());
return_count;
}
privatevoidTravel(TreeNodecurrent,Listret){
if(current==null){
return;
}
if(current.val==_sum){
_count++;
}
varleft=newList();
Travel(current.left,left);
varright=newList();
Travel(current.right,right);
ret.AddRange(left);
ret.AddRange(right);
for(vari=0;i
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！