Leetcode 257. Binary Tree Paths (Python)

Related Topic

Depth-First-Search. Tree. Postorder-Traversal.

Description

Given a binary tree, return all root-to-leaf paths.

Sample I/O

Example 1

Input:

   1
 /   \
2     3
 \
  5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Note

A leaf is a node with no children.

Methodology

This question can be solved by Depth First Search.

We use dfs to traversal the tree in postorder. If the root is none, return [] to the previous root, if the root does not have left child or right child, this root must be a leaf then we return this [root.val] to the previous root. Now the previous root has two pathes one is [] another one is [previous_root->this_root]

Code(DFS)

def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root is None: return
        if root.left is None and root.right is None:
            return [str(root.val)]
        l_path = self.binaryTreePaths(root.left)
        r_path = self.binaryTreePaths(root.right)
        left = [str(root.val)+"->"+node.val for node in l_path]
        right = [str(root.val)+"->"+node.val for node in r_path]
        return left+right

BigO

We traversal all nodes of the tree once so O(n) and we need to append each root value to the answer which takes O(n) so total is O(n^2)