257. Binary Tree Paths

Leetcode Depth-first Search

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:
   1
 /   \
2     3
 \
  5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3

分析

使用DFS+回溯法的思想，寻找路径

public class Q257BinaryTreePaths {
    private List<String> paths = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        binaryTreePathsHelper(root, new StringBuilder());
        return paths;
    }

    public void binaryTreePathsHelper(TreeNode root, StringBuilder s) {
        if (root == null) return;
        String tmp = String.format("%d->", root.val);
        s.append(tmp);
        if (root.left == null && root.right == null){
            paths.add(s.substring(0, s.length() - 2));
            s.delete(s.length() - tmp.length(), s.length());
            return;
        }
        binaryTreePathsHelper(root.left, s);
        binaryTreePathsHelper(root.right, s);
        s.delete(s.length() - tmp.length(), s.length());
    }
}

一种小的修改是首先求出路径，然后再转化为字符串打印；

public class Q257BinaryTreePaths {
    private List<List<Integer>> paths = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        binaryTreePathsHelper(root, new ArrayList<>());
        for (List<Integer> list: paths) {
            StringBuilder s = new StringBuilder();
            for (Integer i: list) {
                s.append(String.format("%d->", i));
            }
            res.add(s.substring(0, s.length() - 2));
        }

        return res;
    }

    public void binaryTreePathsHelper(TreeNode root, List<Integer> list) {
        if (root == null) return;
        list.add(root.val);
        if (root.left == null && root.right == null){
            paths.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        }
        binaryTreePathsHelper(root.left, list);
        binaryTreePathsHelper(root.right, list);
        list.remove(list.size() - 1);
    }
}

运行时间基本一致。

在论坛上发现一个非常优美的方案，直接使用String，而不是StringBuilder，利用参数传递省去了s.delete操作。所以速度反而非常快。

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) {
    String local = path + root.val;
    if (root.left == null && root.right == null) answer.add(local);
    if (root.left != null) searchBT(root.left, local + "->", answer);
    if (root.right != null) searchBT(root.right, local + "->", answer);
}