# Tree 与 BackTracking 的比较

* **Tree 上比较常用的是先 ADD ，然后分别在 leaf node return 之前还有两边 dfs 结束之后 REMOVE**
* **其实就是 pre-order traversal.**
* **其他的 DFS 是 element 已经加好了之后才开始的，而 Tree 是带着当前在考虑的 element 开始的。**

来看两道题，一个是LintCode的 [Permutations](http://www.lintcode.com/en/problem/permutations/)，一个是 LeetCode 的 [Binary Tree Paths](https://leetcode.com/problems/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 (空间占用多一些)，这样可以免去回溯的步骤。

```java
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);
        }
    }
}
```

```java
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 的例子，看起来稍微蛋疼了点；

```java
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 了。

```java
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/search_and_backtracking_sou_suo_yu_hui_su/414.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.