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
1and8500. - Each node in the tree will have a value between
0and25.
struct Solution;
use rustgym_util::*;
trait Preorder {
fn preorder(&self, cur: &mut Vec<char>, min: &mut String);
}
impl Preorder for TreeLink {
fn preorder(&self, cur: &mut Vec<char>, min: &mut String) {
if let Some(node) = self {
let node = node.borrow();
let val = (node.val as u8 + b'a') as char;
cur.push(val);
if node.left.is_none() && node.right.is_none() {
let s: String = cur.iter().rev().copied().collect();
if min.is_empty() {
*min = s;
} else {
if s < *min {
*min = s;
}
}
}
node.left.preorder(cur, min);
node.right.preorder(cur, min);
cur.pop();
}
}
}
impl Solution {
fn smallest_from_leaf(root: TreeLink) -> String {
let mut cur: Vec<char> = vec![];
let mut res: String = "".to_string();
root.preorder(&mut cur, &mut res);
res
}
}
#[test]
fn test() {
let root = tree!(
0,
tree!(1, tree!(3), tree!(4)),
tree!(2, tree!(3), tree!(4))
);
let res = "dba".to_string();
assert_eq!(Solution::smallest_from_leaf(root), res);
let root = tree!(
25,
tree!(1, tree!(1), tree!(3)),
tree!(3, tree!(0), tree!(2))
);
let res = "adz".to_string();
assert_eq!(Solution::smallest_from_leaf(root), res);
let root = tree!(
2,
tree!(2, None, tree!(1, tree!(0), None)),
tree!(1, tree!(0), None)
);
let res = "abc".to_string();
assert_eq!(Solution::smallest_from_leaf(root), res);
}