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:

Image text

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

Output: “dba”

Example 2:

Image text

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

Output: “adz”

Example 3:

Image text

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.

  • /**
     * 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