LeetCode
面试题34. 二叉树中和为某一值的路径
https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

搜索回溯方法：

//搜索回溯方法
class Solution {
    List<List<Integer>> res;

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new LinkedList<>();
        List<Integer> trace = new LinkedList();
        if(root == null) return res;
        search(root, sum, trace);
        return res;
    }

    public void search(TreeNode node, int target, List<Integer> trace) {
        trace.add(node.val);
        //根节点
        if (node.left == null && node.right == null && target == node.val) 
            res.add(new LinkedList<Integer>(trace));
        //不是根节点
        if (node.left != null) search(node.left, target - node.val, trace);
        if (node.right != null) search(node.right, target - node.val, trace);
        trace.remove(trace.size() - 1);
    }
}

模板一：

int search(int k) {
    if (到目的地) {
        输出解;
    } else {
        for (i = 1; i <= 算符种数; i++) {
            if (满足条件) {
                保存结果;
                search(k+1);
                恢复: 保存结果之前的状态 { 回溯一步; }
            }
        } 
    } 
}

模板二

int search(int k) {
    for (i = 1; i <= 算符种数; i++) {
        if (满足条件) {
            保存结果;
            if (到目的地) {
                输出解;
            } else {
                search(k+1);
            }
            恢复: 保存结果之前的状态 { 回溯一步 }
        }
    } 
}