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.
1public class 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 (string.Compare(path, smallest) < 0) smallest = path;
12 }
13 Dfs(node.left, path);
14 Dfs(node.right, path);
15 }
16}This C# implementation carries the same logic as the other DFS solutions. The `smallest` variable is globally assigned to store the least lexicographic string discovered so far. Path strings are created by sucking nodes' character equivalents in front of the current path recursively, followed by comparisons and updates at leaf nodes.