[988][中等][DFS] 从叶结点开始的最小字符串

题目描述

988. 从叶结点开始的最小字符串

给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。

找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）

示例 1：

输入：[0,1,2,3,4,3,4]
输出："dba"

示例 2：

输入：[25,1,3,1,3,0,2]
输出："adz"

示例 3：

输入：[2,2,1,null,1,0,null,0]
输出："abc"

提示：

• 给定树的结点数介于 1 和 8500 之间。

• 树中的每个结点都有一个介于 0 和 25 之间的值。

解题思路

思路仍然是使用DFS进行搜索, 对于每个结点, 分别找到其左右子树代表的最小字符串, 然后比较两个字符串, 选择其中较小的, 作为该节点代表的子树的最小字符串, 向上回溯, 继续比较.

由于字符串代表的路径是从叶子结点向根节点推进的, 因此DFS的停止条件就是遇到了叶子结点, 更近一部, 可以认为是叶子结点的虚拟子节点None. 遇到这种情况, 返回当前路径.

需要注意的是非叶子结点, 但只有单边子树的结点, 即这些结点只有左子树或右子树一棵子树. 这种情况, 由于路径只能从非叶子结点开始, 这种情况就无需比较左右两个子节点代表的路径, 而是直接使用有子树那边的最小路径返回即可.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:
        if root is None:
            return ''

        def dfs(node, path):
            if node is None:
                return path[::-1]

            path = path.copy()
            path.append(node.val)
            left_path = dfs(node.left, path)
            right_path = dfs(node.right, path)
            if node.left is None:
                return right_path
            elif node.right is None:
                return left_path
            else:
                len_left, len_right = len(left_path), len(right_path)
                new_path = None
                for i in range(min(len_left, len_right)):
                    if left_path[i] != right_path[i]:
                        new_path = left_path if left_path[i] < right_path[i] else right_path
                        break
                if new_path is None:
                    new_path = left_path if len_left < len_right else right_path
                return new_path

        smallest = dfs(root, [])
        return ''.join(chr(num + 97) for num in smallest)