废话不多说了,下面和大家分享一下扣丁学堂Java在线学习课程:LeetCode -- Path Sum III分析及实现方法,希望可以帮到对Java开发感兴趣的小伙伴们。

Java在线学习课程:LeetCode——Path Sum III分析及实现方法

Java培训

LeetCode -- Path Sum III分析及实现方法

题目描述:

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

给定一个二叉树,遍历过程中收集所有可能路径的和,找出和等于X的路径树。

思路:

设当前节点为root,分别收集左右节点路径和的集合,merge到当前集合中;

将当前节点添加到数组中,构成新的可能路径。

实现代码:

/**

* Definition for a binary tree node.

* public class TreeNode {

* public int val;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int x) { val = x; }

* }

*/

public class Solution {

private int _sum;

private int _count;

public int PathSum(TreeNode root, int sum)

{

_count = 0;

_sum = sum;

Travel(root, new List<int>());

return _count;

}

private void Travel(TreeNode current, List<int> ret){

if(current == null){

return ;

}

if(current.val == _sum){

_count ++;

}

var left = new List<int>();

Travel(current.left, left);

var right = new List<int>();

Travel(current.right, right);

ret.AddRange(left);

ret.AddRange(right);

for(var i = 0;i < ret.Count; i++){

ret[i] += current.val;

if(ret[i] == _sum){

_count ++;

}

}

ret.Add(current.val);

//Console.WriteLine(ret);

}

}

好了,以上就是小编给大家分享的Java在线学习课程:LeetCode -- Path Sum III分析及实现方法,想要学好Java开发的小伙伴一定要选择专业的Java培训机构,小编给大家推荐专业的Java培训机构扣丁学堂,扣丁学堂不仅有专业的老师和与时俱进的课程体系还有大量的Java在线教程供学员观看学习,心动的小伙伴快快行动吧。