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.
1#include <string>
2using namespace std;
3class Solution {
4public:
5 string smallestFromLeaf(TreeNode* root) {
6 smallest = "~";
7 dfs(root, "");
8 return smallest;
9 }
10private:
11 string smallest;
12 void dfs(TreeNode* node, string path) {
13 if (node == nullptr) return;
14 path = char(node->val + 'a') + path;
15 if (!node->left && !node->right) {
16 if (path < smallest) smallest = path;
17 }
18 dfs(node->left, path);
19 dfs(node->right, path);
20 }
21};The C++ DFS solution involves recursive function calls to traverse from a root down to all leaf nodes. The path string is formed by concatenating the current node character at the beginning of the ongoing path. The smallest string is updated upon encountering a leaf node with a smaller path. The recursive function continues to check down both the left and right children paths.