Friday, August 30, 2019

Leetcode solution 257: Binary Tree Paths

Problem Statement 

Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input:

   1
 /   \
2     3
 \
  5

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

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

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Easy problem. Use pre-order traversal from root to leaf and keep the recursion path. The recursion returning condition would be when a node doesn’t have left and right children. Note use a string to keep appending is easier than using a string builder, because we need to pop out and reset the string builder.

Caveat
  • Handle the single node situation when no "->". E.g.,  A vs A->B
There is also an iterative implementation of this using one stack, similar to BST iterator using one stack problem. 

Solutions

Pre-order traversal


Time Complexity: O(N), each node is visited once
Space Complexity: O(N), N is the total nodes since that's the string length you need

References

No comments:

Post a Comment