diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /smallest_string_leaf.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'smallest_string_leaf.py')
-rw-r--r-- | smallest_string_leaf.py | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/smallest_string_leaf.py b/smallest_string_leaf.py new file mode 100644 index 0000000..184f1ca --- /dev/null +++ b/smallest_string_leaf.py @@ -0,0 +1,43 @@ +# 988. Smallest String Starting From Leaf + +""" +given the 'root' of a binary tree where each node has a value in the range +'[0, 25]' representing 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. a leaf +of a node is a node that has no children. +""" + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + def smallestFromLeaf(self, root): + """ + :type root: TreeNode + :rtype: str + """ + + def dfs(root, s): + s = s + chr(ord("a") + root.val) + if not root.left and not root.right: + if res[0] == None: + res[0] = s[::-1] + else: + res[0] = min(res[0], s[::-1]) + if root.left: + dfs(root.left, s) + if root.right: + dfs(root.right, s) + + if not root: + return "" + ans = [None] + dfs(root, "") + return ans[0] |