Baozi Training Leetcode solution 257: Binary Tree Paths
- 2019 年 10 月 4 日
- 筆記
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
