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

题目

给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。
返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

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

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

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

示例 1：
[中等] 988. 从叶结点开始的最小字符串 - 图1

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

示例 2：
[中等] 988. 从叶结点开始的最小字符串 - 图2

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

示例 3：
[中等] 988. 从叶结点开始的最小字符串 - 图3

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

解答 & 代码

递归回溯

  • DFS 遍历到每个叶子节点时，会得到一条从根节点到当前叶子结点的路径，将路径反转，和结果 result 比较，如果字典序小于结果 result，则更新 result

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. private:
    14.   string result;                    // 结果，从某个叶节点开始到根节点的最小字符串
    15.   string path;                    // 当前路径（从根节点开始）
    17.   // 递归回溯
    18.   void backTrace(TreeNode* root)
    19.   {
    20.       if(root == nullptr)            // 递归结束条件
    21.           return;
    23.       // 前序位置
    24.       path += root->val + 'a';    // 选择
    25.       // 若当前为叶子节点
    26.       if(root->left == nullptr && root->right == nullptr)
    27.       {
    28.           string rPath = path;
    29.           reverse(rPath.begin(), rPath.end());    // 反转路径
    30.           if(result == "" || rPath < result)
    31.               result = rPath;                        // 更新 result
    32.           path.pop_back();        // 撤销选择
    33.           return;
    34.       }
    36.       // 递归处理左、右子树
    37.       backTrace(root->left);
    38.       backTrace(root->right);
    40.       // 后序位置
    41.       path.pop_back();            // 撤销选择
    42.   }
    43. public:
    44.   string smallestFromLeaf(TreeNode* root) {
    45.       result = "";
    46.       path = "";
    47.       backTrace(root);
    48.       return result;
    49.   }
    50. };

    复杂度分析：设二叉树节点数为 n

  • 时间复杂度 O(n)：遍历二叉树的所有节点

  • 空间复杂度 O(log n)：递归栈空间 = 二叉树深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 85.48% 的用户
  4. 内存消耗：18.9 MB, 在所有 C++ 提交中击败了 95.16% 的用户