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.
原文：http://www.cnblogs.com/lishiblog/p/4083065.html