路径与路径和

Binary Tree Paths

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"]

• 用 StringBuilder 传递可以省去递归中新建的 string copies.

• StringBuilder 的回溯也很简单，直接 setLength(int len) 就行。

在 leaf node 上以 sb.setLength() 收尾是为了 backtracking，因为后面的两个 dfs 都没有做，不走到底是不会回溯的，要由到了 leaf node 那一层递归进行处理。这点和常见的 subsets 和 permutations 不太一样，那两题中收尾直接 add 然后 return 就可以了，而回溯在 dfs 之后做。

在 dfs 之后直接 backtracking 会遇到问题，例如路径上某个分叉上只有一边有节点，向 null 方向探索之后会删掉来路。

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

    public void search(TreeNode root, String path, List<String> ans){
        if(root.left==null && root.right==null){
            ans.add(path+root.val); return;
        }
        if(root.left!=null) search(root.left, path+root.val+"->", ans);
        if(root.right!=null) search(root.right, path+root.val+"->", ans);
    }
}