Tree的DFS与Backtracking的比较

Tree上的DFS和Backtracking的主要差别：

1. Tree上DFS要把当前处理的TreeNode作为参数，而Backtracking往往不用，因为element之间没什么等级关系。而且intermediate结果用list存着，或者boolean array也可以用来区分哪些元素已经用过了，不会重复。
2. Tree上的DFS通常在对当前root的每一个child node dfs完后才会remove，而常规的Backtracking（如下面的Permutations）则是每个分支add一次，remove一次。

常规的Backtracking通常有以下步骤：

1. add element
2. DFS
3. remove element

下面是两道典型例题：46. Permutations 和 257. Binary Tree Paths

首先是46. Permutations：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        if (nums == null || nums.length == 0)
            return res;
        backtrack(res, new ArrayList<Integer>(), new HashSet<Integer>(), nums);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> l, Set<Integer> s, int[] nums){
        // 之所以用set是因为在判断一个num是不是已经用过的时候可能会快点
        if (l.size() == nums.length){
            res.add(new ArrayList<>(l));  // 非常重要！！！一定要新建一个list！不然最后返回的res里会全部都是空list
            int last = l.get(l.size()-1);
            // l.remove(l.size()-1);
            // s.remove(last);
            return;
        }
        for (int num : nums){
            if (!s.contains(num)){
                l.add(num);
                s.add(num);
                backtrack(res, l, s, nums);
                int last = l.get(l.size()-1);
                l.remove(l.size()-1);
                s.remove(last);
            }
        }
    }
}

然后是257. Binary Tree Paths：

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

    public void dfs(List<String> res, StringBuilder sb, TreeNode root){
        int len = sb.length();
        sb.append(root.val);
        if (root.left == null && root.right == null){ // leaf node
            res.add(sb.toString());
            sb.setLength(len);
            return;
        }
        sb.append("->");
        if (root.left != null)
            dfs(res, sb, root.left);
        if (root.right != null)
            dfs(res, sb, root.right);
        sb.setLength(len);
    }
}

对于这道题，因为最后要求的是返回一个List，所以在每层dfs递归时，向下层传递一个string作为参数。这样由于string的immutable性质，我们就不用再回溯了：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null)
            return res;
        backtrack(res, "", root);
        return res;
    }

    public void backtrack(List<String> res, String s, TreeNode root){
        s += root.val;
        if (root.left == null && root.right == null){  // leaf node
            res.add(s);
            return;
        }
        s += "->";
        if (root.left != null){
            backtrack(res, s, root.left);
        }
        if (root.right != null){
            backtrack(res, s, root.right);
        }
    }
}