package question;

import java.util.*;

/*
 @author: Roderland
 @create: 2020年09月26日---9:36
*/
public class Question113 {
 public static void main(String[] args) {
 TreeNode t1 = new TreeNode(5);
 TreeNode t2 = new TreeNode(3);
 TreeNode t3 = new TreeNode(3);
 t1.left = t2;
 t1.right = t3;
 System.out.println(new Question113().pathSum(null, 8));
 }

 List<List<Integer>> res = new LinkedList<>();
 Deque<Integer> path = new LinkedList<>();

 public List<List<Integer>> pathSum(TreeNode root, int sum) {
 dfs(root, sum);
 return res;
 }

 private void dfs(TreeNode root, int sum) {
 if (root == null) return;
 sum -= root.val;
 path.offerLast(root.val);
 if (root.left == null && root.right == null && sum == 0) res.add(new LinkedList<>(path));
 dfs(root.left, sum);
 dfs(root.right, sum);
 path.pollLast();
 }

 /*
 List<List<Integer>> res;
 int sum;

 public List<List<Integer>> pathSum(TreeNode root, int sum) {
 res = new ArrayList<>();
 if (root == null) return res;
 this.sum = sum;
 dfs(root, 0);
 return res;
 }

 private int[] dfs(TreeNode root, int s) {
 if (root.left == null && root.right == null) {
 if (s + root.val == sum) {
 List<Integer> list = new LinkedList<>();
 list.add(0, root.val);
 res.add(list);
 return new int[]{res.size() - 1};
 }
 } else {
 int[] leftArray = fun(root.left, s, root.val);
 int[] rightArray = fun(root.right, s, root.val);
 int[] array = new int[leftArray.length + rightArray.length];
 int i = 0;
 for (int num : leftArray) array[i++] = num;
 for (int num : rightArray) array[i++] = num;
 return array;
 }
 return null;
 }

 private int[] fun(TreeNode root, int s, int parentVal) {
 int[] array = null;
 if (root != null) {
 array = dfs(root, s + parentVal);
 if (array != null) {
 for (int index : array) res.get(index).add(0, parentVal);
 }
 }
 return array == null ? new int[0] : array;
 }
 */

}