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:
- The number of nodes in the given tree will be between
1
and8500
. - Each node in the tree will have a value between
0
and25
.
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 }