Tree 与 BackTracking 的比较

• Tree 上比较常用的是先 ADD ，然后分别在 leaf node return 之前还有两边 dfs 结束之后 REMOVE

• 其实就是 pre-order traversal.

• 其他的 DFS 是 element 已经加好了之后才开始的，而 Tree 是带着当前在考虑的 element 开始的。

来看两道题，一个是LintCode的 Permutations，一个是 LeetCode 的 Binary Tree Paths:

二者之间处理 backtracking 的方式和递归结构有细微的差别。

Permutations dfs 传的参数中不包括当前元素； Binary Tree Paths dfs 参数中包含当前考虑的元素；

• 5/25复习注：其实两个都带了当前要考虑的元素，只不过一个是用 index 形式（array），一个是 TreeNode.

Permutations 在 dfs 结束后回溯； Tree Paths 在 leaf node 回溯，在最后一个 dfs 后回溯；

另一个重要区别是，Permutations 是给定 array 的，可以使用 O(1) 的 random index access; 而 tree 不行，每次只能带着当前节点 root 去做 dfs.

DFS + Backtracking 都有三个步骤：

• Add element

• DFS

• Remove element

其中随着 dfs 传递参数的不同，三个步骤的位置会有变化。

在 Tree 上做 dfs + backtracking 比较适合用 dfs 带着当前考虑的 node 为参数，先 Add 然后在 leaf node 上做 Remove 的方式；

在中间结果是 String 的情况下，如果想保存一个 object 的 reference 可以用 StringBuilder, 同时也可以利用 immutable 的性质直接传新的 String copy (空间占用多一些)，这样可以免去回溯的步骤。

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(nums == null || nums.size() == 0) return result;

        helper(result, new ArrayList<Integer>(), nums);
        return result;
    }

    private void helper(ArrayList<ArrayList<Integer>> result, 
                        ArrayList<Integer> list,
                        ArrayList<Integer> nums){

        if(list.size() == nums.size()){
            result.add(new ArrayList<Integer>(list));
            return;
        }          

        for(int i = 0; i < nums.size(); i++){
            if(list.contains(nums.get(i))) continue;
            list.add(nums.get(i));
            helper(result, list, nums);
            // 抹掉末尾
            list.remove(list.size() - 1);
        }
    }
}

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<String>();
        if(root == null) return list;
        dfs(list, root, new StringBuilder());
        return list;
    }

    private void dfs(List<String> list, TreeNode node, StringBuilder sb){
        if(node == null) return;

        // 存盘，记录当前位置
        int length = sb.length();
        ------------ADD-------------
        sb.append(node.val);
        ------------Check--------------
        if(node.left == null && node.right == null){
            list.add(sb.toString());
            // 归位（抹掉最后一个数字）
            sb.setLength(length);
            return;
        }

        -------------DFS---------------
        sb.append("->");
        dfs(list, node.left, sb);
        dfs(list, node.right, sb);
        -----------Backtrack-------------
        // 归位（抹掉最后一个箭头和前面的数字）
        sb.setLength(length);
    }
}

一个先加后 dfs 的例子，看起来稍微蛋疼了点；

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<String>();
        if(root == null) return list;
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        if(root.left == null && root.right == null){
            list.add(sb.toString());
            return list;
        }
        dfs(list, root, sb);
        return list;
    }

    private void dfs(List<String> list, TreeNode node, StringBuilder sb){
        if(node == null) return;

        if(node.left == null && node.right == null){
            list.add(sb.toString());
            return;
        }

        sb.append("->");
        int length = sb.length();
        if(node.left != null){
            sb.append(node.left.val);
            dfs(list, node.left, sb);
            sb.setLength(length);
        }
        if(node.right != null){
            sb.append(node.right.val);
            dfs(list, node.right, sb);
            sb.setLength(length);
        }

    }
}

另一个比较有意思的解法，利用 String immutable 默认生成新 copy 的办法，当你 dfs 之间不是 by reference 指向同一个 object / collection ，也就不需要 backtracking 了。

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if (root == null){
            return res;
        }
        return getPaths (root, "", res);
    }

    public List<String> getPaths(TreeNode root, String str, List<String> res){
        if (root.left == null && root.right == null){
            if (str.equals("")){
                str += root.val;
            } else {
                str += "->"+root.val;
            }
            res.add (str);
            return res;
        }

        if (str.equals("")){
            str += root.val;
        } else {
            str += "->"+root.val;
        }

        if (root.left != null)  getPaths (root.left, str, res);
        if (root.right != null)  getPaths (root.right, str, res);

        return res;
    }
}