# \[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：

![](/files/-MGkLLDMwC6GHURgpX62)

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

示例 2：

![](/files/-MGkLLDOOIog4aVv7F9K)

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

示例 3：

![](/files/-MGkLLDPHSoHeAXBwdNK)

```
输入：[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)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/dfs/988-cong-ye-jie-dian-kai-shi-de-zui-xiao-zi-fu-chuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.