LeetCode 二叉树路径问题 Path SUM(123) 总结
Path Sum II leetcode java https://www.cnblogs.com/springfor/p/3879827.html
描述
- Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
- For example:
- Given the below binary tree and sum = 22,
- 5
- / 4 8
- // 11 13 4
- / \ / 7 2 5 1
- return
- [
- [5,4,11,2],
- [5,8,4,5]
- ]
解析
除了要判断是否有这样的一个 path sum, 还需要把所有的都可能性结果都返回, 所以就用传统的 DFS 递归解决子问题.
将当前节点 root 的值放入 list 中更新 sum 值, 判断当前节点是否满足递归条件 root.left == null && root.right == null&&sum == 0;
若满足, 则将存有当前路径的 list 值存入最后的大 list 中
然后依次递归左子树和右子树
从存有当前路径的 list 中去除最后一个节点, 这样便可以返回到了当前叶子节点的父节点
代码
- /**
- * 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>> listAll = new ArrayList<>();
- List<Integer> list = new ArrayList<>();
- public List<List<Integer>> pathSum(TreeNode root, int sum) {
- if(root == null)
- return listAll;
- list.add(root.val);
- sum -= root.val;
- if(root.left == null && root.right == null && sum == 0)
- listAll.add(new ArrayList<Integer>(list));
- pathSum(root.left, sum);
- pathSum(root.right, sum);
- list.remove(list.size() - 1);
- return listAll;
- }
- }
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public void pathSumHelper(TreeNode root, int sum, List<Integer> sumlist, List<List<Integer>> pathlist) {
- if (root == null)
- return;
- sumlist.add(root.val);
- sum = sum - root.val;
- if (root.left == null && root.right == null) {
- if (sum == 0) {
- pathlist.add(new ArrayList<Integer>(sumlist));
- }
- } else {
- if (root.left != null)
- pathSumHelper(root.left, sum, sumlist, pathlist);
- if (root.right != null)
- pathSumHelper(root.right, sum, sumlist, pathlist);
- }
- sumlist.remove(sumlist.size() - 1);
- }
- public List<List<Integer>> pathSum(TreeNode root, int sum) {
- List<List<Integer>> pathlist = new ArrayList<List<Integer>>();
- List<Integer> sumlist = new ArrayList<Integer>();
- pathSumHelper(root, sum, sumlist, pathlist);
- return pathlist;
- }
- }
[LeetCode] 113. Path Sum II ☆☆☆(二叉树所有路径和等于给定的数)
来源: http://www.bubuko.com/infodetail-3003371.html