aboutsummaryrefslogtreecommitdiff
path: root/smallest_string_leaf.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /smallest_string_leaf.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'smallest_string_leaf.py')
-rw-r--r--smallest_string_leaf.py43
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]