摘要：前言的从叶结点开始的最小字符串给定一颗根结点为的二叉树，书中的每个结点都有一个从到的值，分别代表字母到值代表，值代表，依此类推。
前言
Weekly Contest 122的 从叶结点开始的最小字符串：
解题思路给定一颗根结点为 root 的二叉树，书中的每个结点都有一个从 0 到 25 的值，分别代表字母 "a" 到 "z"：值 0 代表 "a"，值 1 代表 "b"，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）
示例1：
输入：[0,1,2,3,4,3,4] 输出："dba"示例2：
输入：[25,1,3,1,3,0,2] 输出："adz"示例3：
输入：[2,2,1,null,1,0,null,0] 输出："abc"提示：
给定树的结点数介于 1 和 1000 之间。
树中的每个结点都有一个介于 0 和 25 之间的值。
此题可以看做是一种特殊的中序遍历，只是递归的过程中需要比较左右子树值。
实现代码 /**
* 988. 从叶结点开始的最小字符串
* 中序遍历的基础上改造
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
* @param root
* @return
*/
public String smallestFromLeaf(TreeNode root) {
// 节点值为[0,25]，所以需要加上"a"来获得对应的char
char c = (char)("a" + root.val);
if (root.left == null && root.right == null) {//无左右子树
return "" + c;
} else if (root.left == null) {//左子树为空，遍历右子树
String str = smallestFromLeaf(root.right);
return str + c;//
} else if (root.right == null) {//右子树为空，遍历左子树
return smallestFromLeaf(root.left) + c;
} else {//左右子树都不为空
String s1 = smallestFromLeaf(root.left);
String s2 = smallestFromLeaf(root.right);
if (s1.compareTo(s2) < 0) {//比较左右子树的最小字符串
return s1 + c;
} else {
return s2 + c;
}
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/77384.html
摘要：也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因於年提出而得名。 前言 因為比较随心所欲,所以我不按难度分享算法,所以你们会看到有时候顺序有变化,因為我发表的时候会按照难度修改下位置,尽量让你们看的时候能从简单开始,以后每次更新都加个更新时间好了,让你们知道我进度.新增计时函数直观对比效率并且因為资料比较杂,很多都是我个人理解说法,如果有发...
摘要：同样结点树的二叉树，完全二叉树的深度最小。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。 二叉树的概念 二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 showImg(https://seg...
阅读 2528·2021-09-13 10:26
阅读 1819·2021-09-03 10:28
阅读 1793·2019-08-30 15:44
阅读 695·2019-08-29 14:07
阅读 278·2019-08-29 13:12
阅读 2011·2019-08-26 11:44
阅读 2233·2019-08-26 11:36
阅读 1908·2019-08-26 10:19
