1
\$\begingroup\$

Description:

Given a binary tree, return all root-to-leaf paths.

Leetcode

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Code:

class Solution {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        traverse(root, new ArrayList<>(), paths);
        return paths;
    }

    private void traverse(TreeNode root, List<String> path, List<String> paths) {
        if (root == null) return;

        path.add(""+root.val);
        if (root.left == null && root.right == null) {
            paths.add(String.join("->", path));
        }

        traverse(root.left,  path, paths);
        traverse(root.right, path, paths);

        path.remove(path.size() - 1);
    }
}
\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

It's a fine solution. Tracking the values on the path, growing and shrinking while traversing to the leafs, finally adding a concatenated values is natural and easy to understand.

An alternative (and not necessarily better) approach that may perform better is to reduce the string creation, concatenation by replacing the List<String> for path with a StringBuilder, something like:

int length = sb.length();
sb.append("->").append(root.val);

if (root.left == null && root.right == null) {
    paths.add(sb.substring(2));
}

traverse(root.left,  sb, paths);
traverse(root.right, sb, paths);

sb.setLength(length);

This might be premature optimization, and "clever" code. I think your original is fine as is.

\$\endgroup\$
1
  • \$\begingroup\$ I thought about it too but went with the generic approach. Also, I am finding this pattern very easy to understand. \$\endgroup\$ Commented Jun 26, 2018 at 21:49
4
\$\begingroup\$

regarding the translation from int to String

path.add(""+root.val);

This is both unclear and also involves unnecessary String creation. Why not use the "official" conversion method? it clearly states the intention and is more efficient

path.add(String.valueOf(root.val));
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.