[Leetcode] Binary Tree Paths

Problem

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
   1
/
2 3

5
All root-to-leaf paths are:
["1->2->5", "1->3"]

Analysis

  • Recursive constructing the path in bottom up fashion
  • For each node, get its left and right paths recursively, denote them as left and right, then the recursion is
    •  (node.val + (each path in left))
    • (node.val + (each path in right))
  • Time: O(N) where N is the number of nodes in the tree

Code

Leave a Reply