Java solution using String or StringBuilder


  • 1
    Y

    Creating new string for each recursion is simple to implement yet performance is not that good. A good way to approach this problem might be first implement the string version very first, and then tell the interviewer that you can improve the performance using StringBuilder.

    // String
    
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        helper(res, "", root);
        return res;
    }
    
    private void helper(List<String> res, String s, TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            res.add(s + root.val);
            return;
        }
        helper(res, s + root.val + "->", root.left);
        helper(res, s + root.val + "->", root.right);
    }
    
    // StringBuilder
    
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        helper(res, new StringBuilder(), root);
        return res;
    }
    
    private void helper(List<String> res, StringBuilder sb, TreeNode root) {
        if(root == null) {
            return;
        }
        int len = sb.length();
        if(root.left == null && root.right == null) {
            sb.append(root.val);
            res.add(sb.toString());
            sb.setLength(len);
            return;
        }
        sb.append(root.val).append("->");
        helper(res, sb, root.left);
        helper(res, sb, root.right);
        sb.setLength(len);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.