二叉树中和为某一特定值的路径

Problem description

题目：输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.

Examples

Example 1:
Input:
          1
      /         \
	  2          3
       \
        5                       ,        8
Output:["1->2->5"]

Solution

　　采用递归的方法，在字符串中处理->注意可以先增加数字，再当左子树或右子树不为空时，增加->.

Code

public List<String> binaryTreePaths(TreeNode root, int sum) {
    List<String> list = new ArrayList<>();

    if (root == null) {
        return list;
    }

    binaryTreepath(list, root, "", 0, sum);

    return list;
}

 public void binaryTreepath(List<String> list, TreeNode root, String s, int curSum, int sum) {

    curSum += root.val;
    s += root.val;

    if (root.left != null) {
        binaryTreepath(list, root.left, s + "->", curSum, sum);
    }
    if (root.right != null) {
        binaryTreepath(list, root.right, s + "->", curSum, sum);
    }
    if (root.left == null && root.right == null && curSum == sum) {
        list.add(s);
        return;
    }
}