二叉树中和为某一值的路径(中等难度)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //定义成全局变量更加方便
    List<List<Integer>> result = new ArrayList<>();
    //官方建议使用Deque,也就是双端队列
    Deque<Integer> path = new LinkedList<>(); // LinkedList方便添加和移除元素
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) return result;
        //先将根节点加入到我们的路径当中
        path.addLast(root.val);
        backtracking(root, target, root.val);
        return result;
    }
    private void backtracking(TreeNode node, int target, int sum) {
        //定义我们的递归结束条件
        if (node.left == null && node.right == null && sum == target) { // 返回结果时节点须为叶子节点
            result.add(new ArrayList<>(path)); // 生成一个新的array list
            return;
        }
        if (node.left != null) { // 左子节点不为空, DFS左子节点
            path.addLast(node.left.val);
            backtracking(node.left, target, sum + node.left.val);
            // 回溯
            path.removeLast(); 
        }
        if (node.right != null) { // 右子节点不为空, DFS右子节点
            path.addLast(node.right.val);
            backtracking(node.right, target, sum + node.right.val);
            // 回溯
            path.removeLast(); 
        }
        // 左右子节点都为空, sum != target, 什么都不用做
    }
}