2024-04-17 Daily Challenge

Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 17

Description

Smallest String Starting From Leaf

You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.

Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

As a reminder, any shorter prefix of a string is lexicographically smaller.

  • For example, "ab" is lexicographically smaller than "aba".

A leaf of a node is a node that has no children.

 

Example 1:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: root = [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"

 

Constraints:

  • The number of nodes in the tree is in the range [1, 8500].
  • 0 <= Node.val <= 25

Solution

class Solution {
public:
  string smallestFromLeaf(TreeNode* root, string current = "") {
    if(!root) return "";
    current.push_back(root->val + 'a');
    if(!root->left && !root->right) {
      reverse(current.begin(), current.end());
      return current;
    }
    auto left = smallestFromLeaf(root->left, current);
    auto right = smallestFromLeaf(root->right, current);
    return ((left < right && left != "") || right == "") ? left : right;
  }
};