描述
給定一個二叉樹现恼，找出所有路徑中各節(jié)點(diǎn)相加總和等于給定 目標(biāo)值 的路徑。
一個有效的路徑蛮拔，指的是從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑述暂。
樣例
給定一個二叉樹，和 目標(biāo)值 = 5:
1
/ \
2 4
/ \
2 3
返回：
[[1, 2, 2],
[1, 4]]
代碼實(shí)現(xiàn)
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root the root of binary tree
* @param target an integer
* @return all valid paths
*/
// List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
List<Integer> path = new ArrayList<>();
path.add(root.val);
dfs(root, root.val, target, path, result);
return result;
}
private void dfs(TreeNode root, int sum, int target, List<Integer> path,
List<List<Integer>> result) {
// meat leaf
if (root.left == null && root.right == null) {
if (sum == target) {
result.add(new ArrayList<>(path));
}
return;
}
// go left
if (root.left != null) {
path.add(root.left.val);
// not dfs(root, sum+root.left.val, target, path, result);
dfs(root.left, sum+root.left.val, target, path, result);
//去掉上一次加入的節(jié)點(diǎn) dfs
path.remove(path.size()-1);
}
//go right
if (root.right != null) {
path.add(root.right.val);
//not dfs(root, sum+root.right.val, target, path, result);
dfs(root.right, sum+root.right.val, target, path, result);
path.remove(path.size()-1);
}
}
}
