Accepted Java simple solution in 8 lines


  • 156
    V
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> answer = new ArrayList<String>();
        if (root != null) searchBT(root, "", answer);
        return answer;
    }
    private void searchBT(TreeNode root, String path, List<String> answer) {
        if (root.left == null && root.right == null) answer.add(path + root.val);
        if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
        if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
    }

  • 5
    Q

    Your code is so elegant!


  • 2
    E

    Manipulating string directly cost a lot, could you please improve the code using StringBuilder or stack?


  • 16
    W

    I see people interview FB meet this question in phone screen. It's simple. But interviewer will ask you about time complexity. The worst case is not that straight-forward. You should try to construct a tree with that 'worst case'. Assume the number of treeNode is n, you need to provide the big O notation of n.


  • 0

    Your code is easy to unstander ,thank you!


  • 0
    X

    Its a good question. I am thinking it is O(n) time complexity, as every node in the tree is visited once. Am I right?


  • 0
    Y

    @EthanLi that would require backtracking right? which makes the solution complicated.


  • 9
    J

    "StringBuilder" is a mutable object, it will hold its value after returning.Whereas String creates a copy in every recursion, you don't need to worry about the "side-effect" when backtrack.


  • 0
    Y

    I actually tried using StringBuilder, it would require removing 3 characters each recursion, which would a bit hard.


  • 0
    S

    it seems pretty straight-forward to me. the code is a pre-order traversal of the tree, so it's O(n).


  • 6
    L

    Is the time complexity O(n2) because of the string append operations ?

    In Java, string '+' operations are O(n).


  • 1
    M

    Actually, some cases need to remove more than 3 characters such as ->-100.


  • 89
    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
    D

    Thanks for sharing. Good solution mate.


  • 4
    S

    Can anyone tell me why we need to do sb.setLength(len) ?


  • 1
    A

    to backtrack


  • 7
    D

    @xiaocheng2 Every node is visited indeed once. But the string concatenation operation becomes more expensive when going deeper. So in my opinion, the total time complexity is O(nlogn).

    I have tried the binary tree (complete) with four levels, then I get this conclusion. The root is visited #leaves number of times.


  • 0
    G

    each recursion call creates a new string object, so it's not memory efficient.

    if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
    if (root.right != null) searchBT(root.right, path + root.val + "->", answer);


  • 0
    S

    So you visit each node for O(n), but each call requires a concatenation bounded by the height of the tree, so shouldn't the complexity be O(n * h) or in the case of a balanced tree O(n * logn)?


  • 0
    Y

    this is really smart..


Log in to reply
 

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