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/
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
You can find the detailed video tutorial here
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
There is also an iterative implementation of this using one stack, similar to BST iterator using one stack problem.
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