package LeetCode;

import java.util.LinkedList;
import java.util.List;

public class LeetCode113 {

    public class TreeNode {
        int val;
        LeetCode113.TreeNode left;
        LeetCode113.TreeNode right;

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


    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> ans = new LinkedList<>();
            List<Integer> result = new LinkedList<>();
            path(root, sum, ans, result);
            return ans;
        }

        public void path(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> result) {
            if (root == null) return;

            // 先放入temp中
            result.add(new Integer(root.val));

            if (root.left == null && root.right == null && sum == root.val) {

                // 如果是叶子节点，条件也符合，放入结果中
                ans.add(new LinkedList(result));

              /*  result.remove(result.size() - 1);
                return;*/
            } else {
                path(root.left, sum - root.val, ans, result);
                path(root.right, sum - root.val, ans, result);

                //如果不符合，则去除
                result.remove(result.size() - 1);

            }


        }
    }
}