L988 从叶节点开始的最小字符串

树

shenjin3.19考试

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

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

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

解：

• 首先要理解什么是字典序：

单词是按照首字母在字母表中的顺序进行排列的，比如 alpha 在 beta 之前。而第一个字母相同时，会去比较两个单词的第二个字母在字母表中的顺序，比如 account 在 advanced 之前，以此类推。

• 扩充知识点：获得最近换位数的三个步骤：
  1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界
  2.把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
  3.把原来的逆序区域转为顺序

• C++中获得最近换位数的三个步骤：
  cout << "abc" > "aac" << endl;打印true;

• C++ string对象的比较
  s.compare(s2)比较s和s2;返回正数s>s2,负数s s=s1+s2两个字符串直接串联

• 字符类型
  (char)('a'+30)为一个大于z的字符

class Solution {
public:
    string findDic(TreeNode * root,string s){
        if(root == NULL) return (char)('a'+30)+s;
        s = (char)('a'+root->val)+s;
        if(root->left == NULL && root->right== NULL) return s;
        string left = findDic(root->left,s);
        string right= findDic(root->right,s);
        return left.compare(right)<0?left:right;
    }
    string smallestFromLeaf(TreeNode* root) {
        if(root== NULL) return "";
        return findDic(root,"");
    }
};