Binary Tree Paths

Definition for a Binary Tree Node

class TreeNode(object):
    """ Definition of a binary tree node."""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Solution

Complexity

time: $O(n)$
space: $O(n)$ (due to implicit stack space)

def binaryTreePaths(self, root: TreeNode) -> List[str]:
    res = []

    def dfs(root: TreeNode, path: str):
        if not root:
            return
        if path:
            path += '->'
        path += str(root.val)
        if not root.left and not root.right:
            res.append(path)
            return
        dfs(root.left, path)
        dfs(root.right, path)

    dfs(root, '')
    return res