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.

/**  * 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);  } }