算法通关村第十八关——回溯

回溯很大感觉就是多重递归，在递归的题目中，例如斐波那契数列，只需要考虑当前情况以及他的子情况。而在回溯中，要进行很多次递归，并且要对条件进行处理。

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

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

示例：
输入：root=[1,2,3,nu11,5]
输出：["1->2->5"，"1->3"]

class BinaryTreePaths {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();}
}

进入dfs，将当前节点添加到temp列表中，如果是叶子节点，那说明当前分支已经处理完了，像结果列表中添加拼接后的temp列表。

如果不是叶子节点，那么就遍历左子树，右子树，按照前序的顺序来回溯，注意在当前分支结束后，要将最下面的那个节点去掉。