Skip to content

988. Smallest String Starting From Leaf 👍

  • Time: $O(nh)$, where $h = |\texttt{path}| = \text{height(tree)}$ for comparison
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  string smallestFromLeaf(TreeNode* root) {
    string ans;
    dfs(root, "", ans);
    return ans;
  }

 private:
  void dfs(TreeNode* root, string&& path, string& ans) {
    if (root == nullptr)
      return;

    path.push_back(root->val + 'a');

    if (root->left == nullptr && root->right == nullptr) {
      ranges::reverse(path);
      if (ans == "" || ans > path)
        ans = path;
      ranges::reverse(path);  // Roll back.
    }

    dfs(root->left, std::move(path), ans);
    dfs(root->right, std::move(path), ans);
    path.pop_back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public String smallestFromLeaf(TreeNode root) {
    dfs(root, new StringBuilder());
    return ans;
  }

  private String ans = null;

  private void dfs(TreeNode root, StringBuilder sb) {
    if (root == null)
      return;

    sb.append((char) (root.val + 'a'));

    if (root.left == null && root.right == null) {
      final String path = sb.reverse().toString();
      sb.reverse(); // Roll back.
      if (ans == null || ans.compareTo(path) > 0)
        ans = path;
    }

    dfs(root.left, sb);
    dfs(root.right, sb);
    sb.deleteCharAt(sb.length() - 1);
  }
}