Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
Example 1:
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
Example 2:
Input: root = [1]
Output: ["1"]
Constraints:
The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100
My Solution
We can solve this problem by doing a postorder traversal. If the current node is null, we just return an empty list. If the current node is a leaf node, we just create a string with the current node’s value and return. Then we recurse on the left and right subtrees, which give us all the paths from the left and right node to the leaf nodes. We then just add our current node’s value to all these paths and return all the paths to the caller.
The time complexity of this algorithm would be O(n * log2 n) because in the worst case in a complete tree, at every level we have n/2 paths (since there are n/2 leaf nodes) to traverse and the number of elements in the path would be log n at the first level, (log n) - 1 at the second level, …, and 1 node at the leaf. This would be log2n elements. Space complexity would O(n * log n) because the most number of elements we have to store would be at the first level and it would be n/2 paths with log n elements for each path.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> out = new ArrayList<>();
List<String> left = new ArrayList<>();
List<String> right = new ArrayList<>();
if (root == null) {
return out;
}
if (root.left == null && root.right == null) {
out.add(String.valueOf(root.val));
return out;
}
left = binaryTreePaths(root.left);
right = binaryTreePaths(root.right);
for (int i = 0; i < left.size(); i++) {
StringBuilder sb = new StringBuilder(String.valueOf(root.val));
sb.append("->");
sb.append(left.get(i));
out.add(sb.toString());
}
for (int i = 0; i < right.size(); i++) {
StringBuilder sb = new StringBuilder(String.valueOf(root.val));
sb.append("->");
sb.append(right.get(i));
out.add(sb.toString());
}
return out;
}
}