《算法通关村——透析回溯的模板》

《算法通关村——透析回溯的模板》

通过几个题来了解

回溯模板

void backtracking(参数) {
        if (终止条件) {
            存放结果;
            return;
        }
        for (选择本层集合中元素（画成树，就是树节点孩子的大小）){
            处理节点;
            backtracking();
            回溯，撤销处理结果;
        }
    }

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

• 树中节点的数目在范围 [1, 100] 内
• -100 <= Node.val <= 100

题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root,new ArrayList<>());
        return ans;
    }

    private void dfs(TreeNode root ,List<Integer> temp){
        if(root == null){
            return;
        }
        temp.add(root.val);
        // 如果是叶子节点记录结果
        if(root.left == null && root.right == null){
            ans.add(getPathString(temp));
        }
        dfs(root.left,temp);
        dfs(root.right,temp);
        temp.remove(temp.size()-1);
    }

    private String getPathString(List<Integer> temp){
        StringBuilder sb = new StringBuilder();
        sb.append(temp.get(0));
        for(int i = 1;i<temp.size();i++){
            sb.append("->").append(temp.get(i));
        }
        return sb.toString();
    }
    
}

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,new ArrayList<Integer>(),targetSum);
        return result;
    }
    private void dfs(TreeNode root,List<Integer> temp,int targetSum){
        if(root == null ){
            return;
        }
        targetSum -= root.val;
        temp.add(root.val);
        if(root.right == null && root.left == null && targetSum == 0){
            result.add(new LinkedList(temp));
        }
        dfs(root.left,temp,targetSum);
        dfs(root.right,temp,targetSum);
        temp.remove(temp.size() -1 );
    }   
}