原文
https://www.b2bchain.cn/5925.html
//给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 // // 说明: 叶子节点是指没有子节点的节点。 // // 示例: //给定如下二叉树，以及目标和 sum = 22， // // 5 // / \ // 4 8 // / / \ // 11 13 4 // / \ / \ // 7 2 5 1 // // // 返回: // // [ // [5,4,11,2], // [5,8,4,5] //] // // Related Topics 树 深度优先搜索 //leetcode submit region begin(Prohibit modification and deletion) import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<List<Integer>> ans=new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { Deque<Integer> level=new ArrayDeque<>(); if(root==null) return ans; helper(root,sum,level); return ans; } private void helper(TreeNode node,int sum,Deque<Integer> path){ if(node==null) return; //先将当前节点加入之后，才可以继续操作 path.addLast(node.val); sum-=node.val; if(node.left==null && node.right==null && sum==0) { ans.add(new ArrayList<>(path)); // 注意：这里 return 之前必须重置 path.removeLast(); return; } helper(node.left,sum,path); helper(node.right,sum,path); path.removeLast(); } } //leetcode submit region end(Prohibit modification and deletion)
