Java solution using StringBuilder instead of string manipulation.


  • 27
    C
    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> rst = new ArrayList<String>();
            if(root == null) return rst;
            StringBuilder sb = new StringBuilder();
            helper(rst, sb, root);
            return rst;
        }
        
        public void helper(List<String> rst, StringBuilder sb, TreeNode root){
            if(root == null) return;
            int tmp = sb.length();
            if(root.left == null && root.right == null){
                sb.append(root.val);
                rst.add(sb.toString());
                sb.delete(tmp , sb.length());
                return;
            }
            sb.append(root.val + "->");
            helper(rst, sb, root.left);
            helper(rst, sb, root.right);
            sb.delete(tmp , sb.length());
            return;
            
        }
    }

  • 0
    Z

    perfects, your code is very easy to understand,thanks!


  • 0
    C

    sb.deleteCharAt(sb.length() - 1);

    what is this line for? delete the the root.val? what if the root.val is greater than 9 (two digits)
    thanks!


  • 0
    C

    That was inappropriate, I've edited my answer, thank you for bringing it up


  • 1

    I think this is by far the on the best solutions in Java.

    1. If we use str1 + str2 it will bring a lot of unnecessary clones;

    2. If we clone StringBuffer it's as bad as cloning string;

    3. If we do concat root + "for(path : childrenPaths)" in every recursion call, it will not be time efficient;

    4. If we do iteration, the queues are not slick enough in this question.


  • 0
    Y

    Good solution, some nitpicking here: first, sb.delete(tmp , sb.length()), you can also do sb.setLength(tmp), a bit shorter. The last return in the helper function is not needed. But a good solution overall using StringBuilder


  • 0
    H

    sb.append(root.val).append('-').append('>')
    Make it a bit shorter and use less space


  • 0
    O

    why you do pruning when use StringBuilder ? My solution used string manipulation, I did not do pruning, and accepted. Thanks


  • 0
    Y

    @olivia_3 String is immutable, everytime you pass a string, it is a new object. Not the case for StringBuilder, it keeps changing everytime you operator on it.


  • 0
    O

    @yfcheng said in Java solution using StringBuilder instead of string manipulation.:

    @olivia_3 String is immutable, everytime you pass a string, it is a new object. Not the case for StringBuilder, it keeps changing everytime you operator on it.

    Thanks, :) got it


Log in to reply
 

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