Sponsored
Sponsored
In this approach, we utilize depth-first search to explore each path from the leaf to the root. We maintain the current path in a string, which is reversed each time we reach a leaf node. We then compare it to the currently known smallest string, updating the smallest string if the new path is smaller.
Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
1class Solution {
2 private String smallest = "~";
3 public String smallestFromLeaf(TreeNode root) {
4 dfs(root, "");
5 return smallest;
6 }
7 private void dfs(TreeNode node, String path) {
8 if (node == null) return;
9 path = (char)(node.val + 'a') + path;
10 if (node.left == null && node.right == null) {
11 if (path.compareTo(smallest) < 0) smallest = path;
12 }
13 dfs(node.left, path);
14 dfs(node.right, path);
15 }
16}The Java solution employs a recursive DFS approach. A global variable `smallest` initialized to "~" stores the currently known smallest string. As we navigate each node of the tree, we prepend the node's corresponding character to the path and check for leaf nodes. Upon reaching a leaf, we update `smallest` if the current path is lexicographically smaller. The recursive calls continue to explore the node's children.