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 pathSum(TreeNode root, int sum) {
            List ans = new LinkedList();
            List result = new LinkedList();
            path(root, sum, ans, result);
            return ans;
        }

        public void path(TreeNode root, int sum, List ans, List 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);

            }


        }
    }
}