Baozi Training Leetcode solution 257: Binary Tree Paths

Leetcode solution 257: Binary Tree Paths

Blogger:https://blog.baozitraining.org/2019/08/leetcode-solution-257-binary-tree-paths.html

Youtube: https://youtu.be/1Ge9R_L9dt8

博客园: https://www.cnblogs.com/baozitraining/p/11441305.html

B站: https://www.bilibili.com/video/av66230678/

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

• Youtube
• B站

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

 1 private List<String> res; // stores the final output
 2 
 3     public List<String> binaryTreePaths(TreeNode root) {
 4         this.res = new ArrayList<>();
 5         helper(root, "");
 6         return this.res;
 7     }
 8 
 9     // helper function that does basic depth first traversal
10     private void helper(TreeNode root, String str) {
11         if(root == null) {
12             return;
13         }
14 
15         if(root.left==null && root.right==null) // reach a leaf node, thus completes a path and need to add it into the output
16             this.res.add(str + root.val);
17         else {
18             str += root.val + "->";
19             helper(root.left, str);
20             helper(root.right, str);
21         }
22         return;
23     }

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

References

• Leetcode official solution