资讯专栏INFORMATION COLUMN

988-从叶结点开始的最小字符串

fireflow / 3460人阅读

摘要:前言的从叶结点开始的最小字符串给定一颗根结点为的二叉树,书中的每个结点都有一个从到的值,分别代表字母到值代表,值代表,依此类推。

前言

Weekly Contest 122的 从叶结点开始的最小字符串:

给定一颗根结点为 root 的二叉树,书中的每个结点都有一个从 025 的值,分别代表字母 "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"

提示:

给定树的结点数介于 11000 之间。

树中的每个结点都有一个介于 025 之间的值。

解题思路

此题可以看做是一种特殊的中序遍历,只是递归的过程中需要比较左右子树值。

实现代码
   /**
     * 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

相关文章

  • 一些前端算法詳解 --- (不定时更新)

    摘要:也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因於年提出而得名。 前言 因為比较随心所欲,所以我不按难度分享算法,所以你们会看到有时候顺序有变化,因為我发表的时候会按照难度修改下位置,尽量让你们看的时候能从简单开始,以后每次更新都加个更新时间好了,让你们知道我进度.新增计时函数直观对比效率并且因為资料比较杂,很多都是我个人理解说法,如果有发...

    Baaaan 评论0 收藏0
  • js数据结构和算法(三)二叉树

    摘要:同样结点树的二叉树,完全二叉树的深度最小。二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表。 二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 showImg(https://seg...

    DesGemini 评论0 收藏0
  • 堆排序

    摘要:概述堆排序是一种树形选择排序,是对直接选择排序的有效改进。称这个过程为堆排序。步骤实例实现堆排序需解决两个问题如何将个待排序的数建成堆输出堆顶元素后,怎样调整剩余个元素,使其成为一个新堆。 概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进。 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: showImg(https://segmentfault...

    zhoutk 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<