[LeetCode] 257. Binary Tree Paths

Problem : https://leetcode.com/problems/binary-tree-paths/

DFS approach

# 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) -> List[str]:
        
        def dfs(node):
            if node:
                suffix = []
                
                if node.left:
                    suffix += dfs(node.left)
                    
                if node.right:
                    suffix += dfs(node.right)
                
                return [[str(node.val)] + s for s in suffix] if suffix else [[str(node.val)]]
                
        
        return ['->'.join(path) for path in dfs(root)]

Iterative DFS approach

# 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) -> List[str]:
        # dfs
        stack = [(root, [root.val])]
        result = []
        
        while stack:
            node, path = stack.pop()
            
            if not node.left and not node.right:
                result.append('->'.join(map(str, path)))
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
            
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
                
        return result

BFS approach

# 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) -> List[str]:
        queue = deque([[root]]) if root else deque()
        result = []
        
        while queue:
            path = queue.popleft()
            
            if path[-1].left:
                queue.append(path + [path[-1].left])
            if path[-1].right:
                queue.append(path + [path[-1].right])
            
            if not path[-1].left and not path[-1].right:
                result.append(path)
        
        return map(lambda p: '->'.join(p), map(lambda path: map(lambda n: str(n.val), path), result))

Edited on 04/22/2021. Refactor DFS solution by appending suffix collected from lower level.

Edited on 06/06/2021. Add iterative DFS solution.