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

http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca

自己想到的解法，比较弱：

首先找到树中所有的路径，即根节点到所有的叶子节点的路径，然后从中找到和为目标值的那些。

实现如下：

import java.util.*;
import java.util.stream.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        List<List<Integer>> tmp = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        // 先找到所有的路径
        find(root, tmp, stack);
        // 过滤出和为目标值的路径
        List<List<Integer>> x = tmp.stream()
            .filter(l -> l.stream().mapToInt(Integer::intValue).sum() == target)
            .collect(Collectors.toList());
        // 转换成牛客要求的返回值类型
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        for (List<Integer> l : x) {
            ArrayList<Integer> ll = new ArrayList<>(l);
            ret.add(ll);
        }
        return ret;
    }

    private void find(TreeNode root, List<List<Integer>> ret, Stack<Integer> stack) {
        if (root != null) {
            stack.push(root.val);
            if (root.left == null && root.right == null) {
                List<Integer> cur = new ArrayList<Integer>(stack);
                ret.add(cur);
            } else {
                find(root.left, ret, stack);
                find(root.right, ret, stack);
            }
            stack.pop();
        }
    }
}

知识点：

为了便于对List进行过滤，使用了Java 8 Stream API中的Collectors，用了import java.util.stream.*;
List<Integer>对所有元素求和的写法是list.stream().mapToInt(Integer::intValue).sum()

最无语的就是牛客的返回值，为什么要是ArrayList<ArrayList<Integer>>，简直太不专业了，导致主方法驱动程序的最后还要把Stream处理的结果转成牛客要求的返回值类型，真心累。

后来看了题解，发现自己的思路是对的，只不过性能差，先把所有的路劲捞出来，然后过滤，这个就慢了，高效的解法无非是一边遍历一边过滤，同时保证参数类型的一致，又减少了类型转换的开销。

但是发现了一个可以作为本题前置知识点的题目：如何求一棵二叉树的所有路径，其中路径的定义与本题相同。

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(root == null || target < root.val) {
            return ret;
        }
        Stack<Integer> stack = new Stack<>();
        find(root, ret, stack, target);
        return ret;
    }

    private void find(TreeNode root, ArrayList<ArrayList<Integer>> ret, Stack<Integer> stack, int target) {
        if (root != null) { // 也是递归终止条件，上车先系安全带
            stack.push(root.val);
            if (root.left == null && root.right == null) { // 叶子节点
                if (stack.stream().mapToInt(Integer::intValue).sum() == target) {
                    ArrayList<Integer> cur = new ArrayList<Integer>(stack);
                    ret.add(cur);
                }
            } else {
                find(root.left, ret, stack, target);
                find(root.right, ret, stack, target);
            }
            stack.pop();
        }
    }
}

但是为什么实际跑出来性能也那么差呢，跟上面的不减支的性能无异，看来性能差主要出现在Stream API上面。

最后看了排行最高的Java提交，但是我这里提交也只能超过77%的用户，不知道牛客的计时是如何计算的。

import java.util.ArrayList;

public class Solution {
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if(root == null || target < root.val) {
            return list;
        }
        path.add(root.val);
        target -= root.val; // 亮点
        if(target == 0 && root.left == null && root.right == null) {
            list.add(new ArrayList<Integer>(path));
        }
        FindPath(root.left, target);
        FindPath(root.right, target);
        path.remove(path.size() - 1);
        return list;
    }
}

还是非常巧妙的，只用了最简单的数据结构，不过实际意义上的栈我更喜欢用对应的数据结构，而不是用ArrayList去模拟栈。不过对比排行高的提交，我的思路还是太笨重了。