首页 > 代码库 > Leetcode-Path Sum II
Leetcode-Path Sum II
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]]
Solution:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<Integer> curPath = new ArrayList<Integer>(); List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root==null) return res; pathSumRecur(root,sum,curPath,res); return res; } public void pathSumRecur(TreeNode curNode, int residual, List<Integer> curPath, List<List<Integer>> res){ if (curNode.left==null&&curNode.right==null){ if (residual==curNode.val){ List<Integer> newPath = new ArrayList<Integer>(); newPath.addAll(curPath); newPath.add(curNode.val); res.add(newPath); return; } else return; } curPath.add(curNode.val); if (curNode.left!=null) pathSumRecur(curNode.left,residual-curNode.val,curPath,res); if (curNode.right!=null) pathSumRecur(curNode.right,residual-curNode.val,curPath,res); curPath.remove(curPath.size()-1); }}
This is a recursive problem. Record the path from root to current node. If find a valid path at some leaf node, then create a copy of current path, and put it into the result set.
//NOTE: since the curPath is changed at each level, we need to restore it after running the recursion function.
Leetcode-Path Sum II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。