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\$
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\$
  • \$\begingroup\$ I thought about it too but went with the generic approach. Also, I am finding this pattern very easy to understand. \$\endgroup\$ – CodeYogi Jun 26 '18 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.