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.
"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:
[1, 8500].0 <= Node.val <= 25In this approach, we utilize depth-first search to explore each path from the leaf to the root. We maintain the current path in a string, which is reversed each time we reach a leaf node. We then compare it to the currently known smallest string, updating the smallest string if the new path is smaller.
This solution uses a DFS approach to explore all paths from leaf nodes to the root. We build the path string by prepending the current node's character (converted from the node's value) to the path. Upon reaching a leaf node, we compare the constructed path to the smallest recorded path. If it's smaller, we update our smallest value. Finally, we use recursion to explore both left and right children of each node.
Java
C++
C
C#
JavaScript
Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
Smallest String Starting From Leaf - Leetcode 988 - Python • NeetCodeIO • 11,197 views views
Watch 9 more video solutions →Practice Smallest String Starting From Leaf with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor