Binary Tree Paths

https://leetcode.com/problems/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)O(n)
  • space: O(n)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
Last Updated: 7/19/2020, 3:45:14 PM