题解 | #二叉树中和为某一值的路径(二)#

import java.util.ArrayList;
import java.util.LinkedList;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if(root == null) {
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        LinkedList<LinkedList<Integer>> res = new LinkedList<>();
        LinkedList<Integer> tmpNums = new LinkedList<>();
        tmpNums.addLast(root.val);
        res.addLast(tmpNums);
        while(!queue.isEmpty()) {
            int sz = queue.size();
            for(int i = 0; i < sz; i++) {
                TreeNode tmp = queue.removeFirst();
                tmpNums = res.removeFirst();
                if(tmp.left == null && tmp.right == null) {
                    int szNums = tmpNums.size();
                    int tmpSum = 0;
                    for(int j = 0; j < szNums; j++) {
                        int tmpNum = tmpNums.removeFirst();
                        tmpSum += tmpNum;
                        tmpNums.addLast(tmpNum);
                    }
                    if(tmpSum == target) {
                        ArrayList<Integer> t = new ArrayList<>();
                        while(!tmpNums.isEmpty()) {
                            t.add(tmpNums.removeFirst());
                        }
                        ans.add(t);
                    }
                    continue;    
                }
                if(tmp.left != null) {
                    LinkedList<Integer> tmpLeNums = new LinkedList<>();
                    int szNums = tmpNums.size();
                    for(int j = 0; j < szNums; j++) {
                        int tmpNum = tmpNums.removeFirst();
                        tmpNums.addLast(tmpNum);
                        tmpLeNums.addLast(tmpNum);
                    }
                    tmpLeNums.addLast(tmp.left.val);
                    res.addLast(tmpLeNums);
                    queue.addLast(tmp.left);
                }
                if(tmp.right != null) {
                    LinkedList<Integer> tmpLeNums = new LinkedList<>();
                    int szNums = tmpNums.size();
                    for(int j = 0; j < szNums; j++) {
                        int tmpNum = tmpNums.removeFirst();
                        tmpNums.addLast(tmpNum);
                        tmpLeNums.addLast(tmpNum);
                    }
                    tmpLeNums.addLast(tmp.right.val);
                    res.addLast(tmpLeNums);
                    queue.addLast(tmp.right);
                }
            }
        }
        return ans;
    }
}