Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/
2 3

5
All root-to-leaf paths are:
["1->2->5", "1->3"]
["1->2->5", "1->3"]

这是一道送分题，dfs就好了。但是，送分题也有值得思考的地方。。。这题我用String作参数很快就AC了，但之后尝试用StringBuilder来做dfs参数（因为不用每次递归都生成一个新的String对象，相对节省空间），写了好几次都没法AC。上班要迟到了。。晚上回来再想一下StringBuilder的实现。

用String作dfs参数：

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

    private void dfs(List<String> res, TreeNode root, String item) {
        if (root == null) return;
        if (isLeaf(root)) {
            item += root.val;
            res.add(item);
            return;
        }
        dfs(res, root.left, item + root.val  + "->");
        dfs(res, root.right, item + root.val + "->" );
    }

    private boolean isLeaf(TreeNode node) {
        return (node != null && node.left == null && node.right == null);
    }

下班了。

今天吃完了饭，八点到家的。。腹肌+洗漱+玩手机又十点了。。。。怎么办啊我这执行力。明天回来应该把手机丢一边了。

贴一下用StringBuilder做的代码吧，但是这个代码是不能AC的，因为我没有append"->"箭头符号进去，箭头符号append进去的话，恢复现场就比较困难。。想恢delete后三位，却总是错乱。索性放弃了。值得注意的是，在发现是node是leaf的时候，也要执行删除结点操作，总之就是每次add完了都要对应一个delete。这写法跟generate parentheses很像。

    private void dfs(List<String> res, TreeNode root, StringBuilder sb) {
        if (isLeaf(root)) {
            sb.append(root.val);
            res.add(new String(sb));
            sb.deleteCharAt(sb.length() - 1);
            return;
        }

        if (root.left != null) {
            sb.append(root.val).append("->");
            dfs(res, root.left, sb);
            sb.deleteCharAt(sb.length() - 1);
        }

        if (root.right != null) {
            sb.append(root.val).append("->");
            dfs(res, root.right, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

Leetcode的高票答案:

总体还是dfs。他这种写法就像surrounded regions的dfs一样，在判断下一层满足之后才进入下一层，可以避免很多次递归。

public List<String> binaryTreePaths(TreeNode root) {
    List<String> answer = new ArrayList<String>();
    if (root != null) searchBT(root, "", answer);
    return answer;
}
private void searchBT(TreeNode root, String path, List<String> answer) {
    if (root.left == null && root.right == null) answer.add(path + root.val);
    if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
    if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
}

(最近几题是按照dfs 的tag来做的，但是遇到有比较复杂定义的题目，比如courses schedule之类几道graph类型的题目就跳过了。。所以总是遇到binary tree的题目。)