题目描述
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"
提示:
树中的每个结点都有一个介于 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)