0988. 从叶结点开始的最小字符串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS 遍历

1. 📝 题目描述

• leetcode

给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。

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

注：字符串中任何较短的前缀在字典序上都是较小的：

• 例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。

节点的叶节点是没有子节点的节点。

---

示例 1：

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

---

示例 2：

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

---

示例 3：

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

---

提示：

• 给定树的结点数在 [1, 8500] 范围内
• 0 <= Node.val <= 25

2. 🎯 s.1 - DFS 遍历

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var smallestFromLeaf = function (root) {
  let result = null

  const dfs = (node, path) => {
    if (!node) return

    // 将当前节点的字符添加到路径前面（因为是从叶到根）
    path = String.fromCharCode(97 + node.val) + path

    // 如果是叶子节点，更新结果
    if (!node.left && !node.right) {
      if (result === null || path < result) {
        result = path
      }
      return
    }

    // 递归遍历左右子树
    dfs(node.left, path)
    dfs(node.right, path)
  }

  dfs(root, '')
  return result
}

• 时间复杂度：$O(n^2)$，其中 n 是树中节点数量，每个叶节点路径拼接字符串的时间为 $O(h)$，h 为树的高度
• 空间复杂度：$O(h)$，递归栈的深度最大为树的高度

算法思路：

• DFS 遍历：从根节点开始深度优先搜索，记录从根到当前节点的路径
• 路径构建：将当前节点的字符添加到路径前面，因为结果字符串是从叶到根的顺序
• 叶节点判断：当遇到叶子节点时（无左右子树），将当前路径与已有结果比较
• 字典序比较：使用字符串比较运算符直接比较字典序，更新最小结果
• 递归遍历：对左右子树递归调用 DFS，传递当前路径字符串