Java solution using StringBuilder instead of string manipulation.


  • 29
    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


  • 0
    N

    I thought there is no need to check if root is null in original method. Also if you have got the length of StringBuilder, setLength is more clear than delete.

    class Solution {
        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 temp, TreeNode root){
            if (root == null) return;
            if (root.left == null && root.right == null) {
                temp.append(root.val);
                res.add(temp.toString());
                return;
            }
            
            temp.append(root.val);
            temp.append("->");
            int curLength = temp.length();
            
            helper(res, temp, root.left);
            temp.setLength(curLength);
            helper(res, temp, root.right);
            temp.setLength(curLength);
        }
        
    }
    

Log in to reply
 

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