> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/dfs/988-cong-ye-jie-dian-kai-shi-de-zui-xiao-zi-fu-chuan.md).

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

## 题目描述

[988. 从叶结点开始的最小字符串](https://leetcode-cn.com/problems/smallest-string-starting-from-leaf/)

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

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

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

示例 1：

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2Fe858b9aa88d9caec6f635769fa58658c2986d40b.png?generation=1599612744903636\&alt=media)

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

示例 2：

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2Fb38b858688b4631d79a2739b3be27f4a0ad429ad.png?generation=1599612744699055\&alt=media)

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

示例 3：

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2F9d621d7a371a40362acc6ef50c2cb63486296e01.png?generation=1599612744791662\&alt=media)

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

提示：

* 给定树的结点数介于 1 和 8500 之间。
* 树中的每个结点都有一个介于 0 和 25 之间的值。

## 解题思路

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

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

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

```python
# 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)
```