Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/988.html

988. Smallest String Starting From Leaf

Level

Medium

Description

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find 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: [0,1,2,3,4,3,4]

Output: “dba”

Example 2:

Input: [25,1,3,1,3,0,2]

Output: “adz”

Example 3:

Input: [2,2,1,null,1,0,null,0]

Output: “abc”

Note:

1. The number of nodes in the given tree will be between 1 and 8500.
2. Each node in the tree will have a value between 0 and 25.

Solution

Do breadth first search. Initially, for each node, the string is reversed, which means the string starts from root and ends at the current node. If a leaf is met, reverse the string and update the smallest string starting from leaf. Finally, return the smallest string.

• Java
• C++
• Python
• Go

• /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode(int x) { val = x; }
   * }
   */
  class Solution {
      String smallestStr = "";
  
      public String smallestFromLeaf(TreeNode root) {
          if (root == null)
              return smallestStr;
          Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
          Queue<StringBuffer> strQueue = new LinkedList<StringBuffer>();
          nodeQueue.offer(root);
          strQueue.offer(new StringBuffer(String.valueOf((char) ('a' + root.val))));
          while (!nodeQueue.isEmpty()) {
              TreeNode node = nodeQueue.poll();
              StringBuffer sb = strQueue.poll();
              TreeNode left = node.left, right = node.right;
              if (left == null && right == null) {
                  sb.reverse();
                  String str = sb.toString();
                  if (smallestStr.length() == 0 || str.compareTo(smallestStr) < 0)
                      smallestStr = str;
                  sb.reverse();
              } else {
                  if (left != null) {
                      StringBuffer leftSB = new StringBuffer(sb.toString());
                      leftSB.append((char) ('a' + left.val));
                      nodeQueue.offer(left);
                      strQueue.offer(leftSB);
                  }
                  if (right != null) {
                      StringBuffer rightSB = new StringBuffer(sb.toString());
                      rightSB.append((char) ('a' + right.val));
                      nodeQueue.offer(right);
                      strQueue.offer(rightSB);
                  }
              }
          }
          return smallestStr;
      }
  }
  

• // OJ: https://leetcode.com/problems/smallest-string-starting-from-leaf/
  // Time: O(N + (logN)^2)
  // Space: O(logN)
  class Solution {
      string ans, path;
      void dfs(TreeNode *root) {
          if (!root) return;
          path += 'a' + root->val;
          if (!root->left && !root->right) {
              reverse(begin(path), end(path));
              if (ans.empty() || path < ans) ans = path;
              reverse(begin(path), end(path));
          } else {
              dfs(root->left);
              dfs(root->right);
          }
          path.pop_back();
      }
  public:
      string smallestFromLeaf(TreeNode* root) {
          dfs(root);
          return ans;
      }
  };
  

• # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class Solution:
      def smallestFromLeaf(self, root: TreeNode) -> str:
          ans = chr(ord('z') + 1)
  
          def dfs(root, path):
              nonlocal ans
              if root:
                  path.append(chr(ord('a') + root.val))
                  if root.left is None and root.right is None:
                      ans = min(ans, ''.join(reversed(path)))
                  dfs(root.left, path)
                  dfs(root.right, path)
                  path.pop()
  
          dfs(root, [])
          return ans
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
      def smallestFromLeaf(self, root):
          """
          :type root: TreeNode
          :rtype: str
          """
          res = []
          self.dfs(root, "", res)
          res.sort()
          return res[0]
      
      def dfs(self, root, path, res):
          if not root.left and not root.right:
              res.append(chr(root.val + ord('a')) + path)
              return
          if root.left:
              self.dfs(root.left, chr(root.val + ord('a')) + path, res)
          if root.right:
              self.dfs(root.right, chr(root.val + ord('a')) + path, res)
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func smallestFromLeaf(root *TreeNode) string {
  	ans := ""
  	var dfs func(root *TreeNode, path string)
  	dfs = func(root *TreeNode, path string) {
  		if root == nil {
  			return
  		}
  		path = string('a'+root.Val) + path
  		if root.Left == nil && root.Right == nil {
  			if ans == "" || path < ans {
  				ans = path
  			}
  			return
  		}
  		dfs(root.Left, path)
  		dfs(root.Right, path)
  	}
  
  	dfs(root, "")
  	return ans
  }
  

All Problems

All Solutions