輸入一棵二叉樹和一個整數省有，打印出二叉樹中節(jié)點值的和為輸入整數的所有路徑澜掩。從樹的根節(jié)點開始往下一直到葉節(jié)點所經過的節(jié)點形成一條路徑。
示例:
給定如下二叉樹芹敌，以及目標和 sum = 22痊远，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示：
節(jié)點總數 <= 10000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權氏捞，非商業(yè)轉載請注明出處碧聪。
一、題解
1.1 思路
本題是典型的二叉樹搜索問題液茎，采用回溯法逞姿，包括先序遍歷 + 路徑記錄。
先序遍歷：按照“根-左-右”的方式遍歷節(jié)點豁护；
路徑記錄：在先序遍歷中哼凯，如果滿足：
當前路徑為根節(jié)點到葉子節(jié)點的一條路徑
-
當前路徑的和等于目標和
就將當前路徑加入res中。
helper()算法流程：
（1）終止條件：當前節(jié)點為null楚里，返回
（2）遞推條件：
- 路徑更新：將當前節(jié)點加入路徑断部；
- 目標值更新：sum = sum - root.val；
- 路徑記錄：當前路徑滿足條件班缎，則加入res蝴光；
- 先序遍歷：遞歸遍歷左右子樹；
- 路徑恢復：向上回溯前达址，將當前節(jié)點從路徑中刪除
1.2 代碼
/**
* 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>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null)
return res;
helper(root, sum, new ArrayList<Integer>());
return res;
}
private void helper(TreeNode root, int sum, ArrayList<Integer> list){
if(root == null){
return;
}
list.add(root.val);
sum = sum - root.val;
if(root.left == null && root.right == null && sum == 0){
res.add(new ArrayList<Integer>(list));
}
helper(root.left, sum, list);
helper(root.right, sum, list);
list.remove(list.size() - 1);
}
}
