【Leetcode Daily】988从叶结点开始的最小字符串

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二叉树，找从叶节点到根节点形成的字符串中，字典序最小的那个。

思路分享

• 官方题解镇楼

  https://leetcode.cn/problems/smallest-string-starting-from-leaf/solutions/3603/cong-xie-jie-dian-kai-shi-de-zui-xiao-zi-fu-chuan-/

• 本题难在字典序的判断，真正的规则是，优先判断字母的大小是否满足，只要前面的某个字母小，就是字典序小。如果前面的字母都相同，就取长度更小的。只要明白了这一点，剩下就是 dfs 遍历然后搜集字符串比较的过程。

代码解答（强烈建议自行解答后再看）

• 参考题解

# 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 compare(self, s1:str, s2:str) -> bool:
        for x, y in zip(s1, s2):
            if x < y:
                return True
            elif x > y:
                return False
        return len(s1) < len(s2)
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        ans = "z"*8501
        def dfs(root:Optional[TreeNode], prefix:str):
            if not root:
                return
            cur_str = prefix + chr(root.val + ord('a'))
            
            if not root.left and not root.right:
                nonlocal ans
                # print(cur_str, len(cur_str), len(ans), cur_str < ans)
                tmp = cur_str[::-1]
                # print(tmp)
                if self.compare(tmp, ans):
                    ans = tmp
            dfs(root.left, cur_str)
            dfs(root.right, cur_str)
        dfs(root, "")
        return ans