257. Binary Tree Paths

https://leetcode.com/problems/binary-tree-paths/

time: O(n)

space: O(n)

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) return res;
        helper(root, res, "");
        return res;
    }
    private void helper(TreeNode root, List<String> res, String path) {
        if (root == null) return; //terminator 1
        path += root.val;
        if (root.left == null && root.right == null) { //terminator 2
            res.add(path);
        }
        helper(root.left, res, path + "->");   //drill down
        helper(root.right, res, path + "->");  //drill down
    }
}

using StringBuilder is faster

如果不另外複製一個 sb來用的話, 會變成這樣, sb 會持續被加上資料

Output Data
["1->2->5","1->2->5->3"]
Expected
["1->2->5","1->3"]

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        helper(root, res, new StringBuilder());
        return res;
    }
    private void helper(TreeNode root, List<String> res, StringBuilder sb) {
        if (root == null) { // terminator 1
            return;
        }
        sb.append(root.val);
        if (root.left == null && root.right == null) { // terminator 2
            res.add(sb.toString());
        }
        sb.append("->");
        String sbTemp = sb.toString(); // if use sb, it should create another sb object to run
        
        helper(root.left, res, sb);  // drill down
        helper(root.right, res, new StringBuilder(sbTemp)); // drill down
    }
}