Leetcode113. 경로 총 II

 ，  sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
 :

[
   [5,4,11,2],
   [5,8,4,5]
]

 /**
     *  
     *
     * @param root
     * @param sum
     * @return
     */
    public static List<List<Integer>> pathSum(TreeNode root, int sum) {

        List<List<Integer>> list = new ArrayList<>();
        ArrayList<Integer> tmp = new ArrayList<>();

        path(root, sum, list, tmp);

        return list;
    }

    private static void path(TreeNode root, int sum, List<List<Integer>> list, ArrayList<Integer> tmp) {
        if (root == null) {
            return;
        }

        tmp.add(root.value);
        if (root.left == null && root.right == null && sum == root.value) {
            //   new  ,  tmp
            list.add(new ArrayList<>(tmp));
        }

        path(root.left, sum - root.value, list, tmp);
        path(root.right, sum - root.value, list, tmp);
        //  : 
        tmp.remove(tmp.size() - 1);
    }

 /**
     *  
     *
     * @param root
     * @param sum
     * @return
     */
    public static List<List<Integer>> pathSum2(TreeNode root, int sum) {

        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Stack<Pair<TreeNode, Integer>> stack1 = new Stack<>();
        stack1.push(new Pair<>(root, sum - root.value));

        Stack<List<Integer>> stack2 = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.value);
        stack2.push(list);

        while (!stack1.isEmpty()) {
            Pair<TreeNode, Integer> pop = stack1.pop();
            TreeNode node = pop.getKey();
            Integer value = pop.getValue();

            List<Integer> pop1 = stack2.pop();
            if (node.left == null && node.right == null && value == 0) {
                res.add(pop1);
            }

            if (node.left != null) {
                stack1.add(new Pair<>(node.left, value - node.left.value));
                List<Integer> list1 = new ArrayList<>();
                list1.addAll(pop1);
                list1.add(node.left.value);
                stack2.push(list1);
            }
            if (node.right != null) {
                stack1.add(new Pair<>(node.right, value - node.right.value));
                List<Integer> list2 = new ArrayList<>();
                list2.addAll(pop1);
                list2.add(node.right.value);
                stack2.push(list2);
            }

        }
        return res;
    }