Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

988. Smallest String Starting From Leaf

Time: $O(nh)$, where $h = |\texttt{path}| = \text{height(tree)}$ for comparison

Space: $O(h)$

			


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) {
      reverse(begin(path), end(path));
      if (ans == "" || ans > path)
        ans = path;
      reverse(begin(path), end(path));  // Roll back
    }

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




			


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);
  }
}