Can't figure out how to stop returning list inside of list (leetcode problem)

user_10699882 0
Viewed 69

Returning list inside of list (not desired)

I keep returning a list inside of a list for the following LeetCode Problem 257. Binary Tree Paths, which is not what the problem wants. I always seem to run into this issue while solving traversal problems.

Here is my current solution along with it's output.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def binaryTreePaths(self, root: TreeNode, val: str="") -> List[str]:
        if not root:
            return ""
        val += str(root.val) + "->"
        if not root.left and not root.right:
            return val[:-2]
        return [path for path in [self.binaryTreePaths(root.left, val), self.binaryTreePaths(root.right, val)] if path]

Input: [1,2,3,null,5]

Output: [["1->2->5"],"1->3"]

Expected: ["1->2->5","1->3"]

Things I've tried

  1. Creating a res variable and using res.extend()
res = []
res.extend(path for path in [self.binaryTreePaths(root.left, val), self.binaryTreePaths(root.right, val)] if path)
  1. Using append instead of extend along with conditionals to try and filter out unwanted elements.

I constantly run into this problem while solving traversal problems so if anyone here has a solution along with some general advice on how to develop an intuition on what's going wrong here and how to solve it in the future, I'd be extremely grateful for your help.

Edit

Well I kept working at trying to fix my solution and after about ~20 minutes, I came up with the following abomination.

class Solution:
    def binaryTreePaths(self, root: TreeNode, val: str="") -> List[str]:
        if not root:
            return ""
        val += str(root.val) + "->"
        if not root.left and not root.right:
            return val[:-2]
        r1 = self.binaryTreePaths(root.left, val)
        r2 = self.binaryTreePaths(root.right, val)
        if isinstance(r1, str):
            r1 = [r1]
        if isinstance(r2, str):
            r2 = [r2]
        for i in r1:
            if i == "":
                r1.pop(r1.index(i))
        for i in r2:
            if i == "":
                r2.pop(r2.index(i))
        return r1 + r2

I'm by no means satisfied with my solution as is so if you know of a cleaner fix please continue to post your fix/advice.

return python-3.x list python
2 Answers

The root issue is that the binaryTreePaths function returns different types depending on the conditions. If root is falsy or when there is no left or right set, it returns just a string ("" or val[:-2]), but in all other cases it returns a list.

The list is only needed for the first level of regression (when returning the final value back to the caller), but the way it is setup it can also return a list from any level of recursion. So, any recursion that also meets the criteria to return the list comprehension will end up with a list within a list at the lower levels of recursion.

So, when you travel more than one node, it will be encased in a list for each additional node. Thus, "1->3" isn't in a list because it was immediately returned as a string after the first recursion on the right side, but "1->2->5" was in a list because there was one extra level of recursion before the string was returned.

There are multiple ways to resolve this - you could track the level of regression and only respond with left/right strings at any depth above 1, then return the list only from level 1, for example. Or you could have a parent function that handles the first layer and a helper function (perhaps a child function within it) that does the recursion part.

Half the fun is figuring it out - so I leave the code piece to you. Hopefully this gave you to tools to resolve it yourself (per the second half of your question). The key is to construct at each recursion level exactly what the return value is. The best way to do this in real-time is to run your code in debugging mode, putting a breakpoint at the start of the recursive function, and follow the code through, and look at what the actual arguments and return values are as it recurses. Do this a few times and you will start to be able to think your way through what is happening without the debugging.

(edit: another trick you can use is writing out the list comprehension long-form - with for loops and if/else statements. It's not as compact, but usually makes it easier to understand which values get assigned when.)

user_65011410

For this problem, we can use stack. This'd get accepted:

class Solution:
    def binaryTreePaths(self, root):
        if not root:
            return []

        paths = []
        stack = [(root, '')]
        while stack:
            node, path = stack.pop()
            if not node.left and not node.right:
                paths.append(f'{path}{node.val}')

            if node.right:
                stack.append((node.right, f'{path}{node.val}->'))

            if node.left:
                stack.append((node.left, f'{path}{node.val}->'))

        return paths

Here is also LeetCode's recursive solution:

 class Solution:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def construct_paths(root, path):
            if root:
                path += str(root.val)
                if not root.left and not root.right:  # if reach a leaf
                    paths.append(path)  # update paths  
                else:
                    path += '->'  # extend the current path
                    construct_paths(root.left, path)
                    construct_paths(root.right, path)

        paths = []
        construct_paths(root, '')
        return paths

References

  • For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis1, 2 in there.
user_65533280
Related