Java 2ms solution using StringBuilder


  • 4
    Y

    The time complexity for the problem should be O(n), since we are basically visiting each node in the tree. Yet an interviewer might ask you for further optimization when he or she saw a string concatenation. A string concatenation is just too costly. A StringBuilder can be used although a bit tricky since it is not immutable like string is.

    When using StringBuilder, We can just keep track of the length of the StringBuilder before we append anything to it before recursion and afterwards set the length back. Another trick is when to append the "->", since we don't need the last arrow at the end of the string, we only append it before recurse to the next level of the tree. Hope the solution helps!

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

  • 0

    My java recursion solution:

    public class Solution {
        
        List<String> result = new ArrayList();
        public List<String> binaryTreePaths(TreeNode root) {
            if(root == null) return result;
            runAtNode(root,""); 
            return result;                        
        }
        
        private void runAtNode(TreeNode node, String parentPath){
            String currentPath = null;
            if(parentPath != ""){
                currentPath = parentPath + "->" + node.val;
            } else{
                currentPath = parentPath + node.val;
            }
            
            if(node.left != null){
                runAtNode(node.left, currentPath);
            }
            if(node.right != null){
                runAtNode(node.right, currentPath);
            }
            
            if(node.left ==null && node.right == null){
                result.add(currentPath);
            }
        }
    }

  • 0
    J

    Good explanation. I was creating a new 'StringBuilder' in every recursion. it's 3ms. Thanks for your sharing!


  • 0
    Y

    Sure, but my point is using StringBuilder. Using string concatenation is not efficient.


  • 0
    S

    How the stringBuilder.setLength() works? My code is almost the same with you, except the sb.setLength(). Didn't get why this saves the code.


Log in to reply
 

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