資訊專欄INFORMATION COLUMN
摘要：前言的從葉結(jié)點(diǎn)開始的最小字符串給定一顆根結(jié)點(diǎn)為的二叉樹，書中的每個(gè)結(jié)點(diǎn)都有一個(gè)從到的值，分別代表字母到值代表，值代表，依此類推。
前言
Weekly Contest 122的 從葉結(jié)點(diǎn)開始的最小字符串：
解題思路給定一顆根結(jié)點(diǎn)為 root 的二叉樹，書中的每個(gè)結(jié)點(diǎn)都有一個(gè)從 0 到 25 的值，分別代表字母 "a" 到 "z"：值 0 代表 "a"，值 1 代表 "b"，依此類推。
找出按字典序最小的字符串，該字符串從這棵樹的一個(gè)葉結(jié)點(diǎn)開始，到根結(jié)點(diǎn)結(jié)束。
（小貼士：字符串中任何較短的前綴在字典序上都是較小的：例如，在字典序上 "ab" 比 "aba" 要小。葉結(jié)點(diǎn)是指沒有子結(jié)點(diǎn)的結(jié)點(diǎn)。）
示例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"提示：
給定樹的結(jié)點(diǎn)數(shù)介于 1 和 1000 之間。
樹中的每個(gè)結(jié)點(diǎn)都有一個(gè)介于 0 和 25 之間的值。
此題可以看做是一種特殊的中序遍歷，只是遞歸的過程中需要比較左右子樹值。
實(shí)現(xiàn)代碼 /**
* 988. 從葉結(jié)點(diǎn)開始的最小字符串
* 中序遍歷的基礎(chǔ)上改造
* 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) {
// 節(jié)點(diǎn)值為[0,25]，所以需要加上"a"來獲得對(duì)應(yīng)的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;
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/77384.html
摘要：也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因於年提出而得名。 前言 因?yàn)楸容^隨心所欲,所以我不按難度分享算法,所以你們會(huì)看到有時(shí)候順序有變化,因?yàn)槲野l(fā)表的時(shí)候會(huì)按照難度修改下位置,盡量讓你們看的時(shí)候能從簡(jiǎn)單開始,以后每次更新都加個(gè)更新時(shí)間好了,讓你們知道我進(jìn)度.新增計(jì)時(shí)函數(shù)直觀對(duì)比效率并且因?yàn)橘Y料比較雜,很多都是我個(gè)人理解說法,如果有發(fā)...
摘要：同樣結(jié)點(diǎn)樹的二叉樹，完全二叉樹的深度最小。二叉樹每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。 二叉樹的概念 二叉樹（Binary Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。 showImg(https://seg...
摘要：概述堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。稱這個(gè)過程為堆排序。步驟實(shí)例實(shí)現(xiàn)堆排序需解決兩個(gè)問題如何將個(gè)待排序的數(shù)建成堆輸出堆頂元素后，怎樣調(diào)整剩余個(gè)元素，使其成為一個(gè)新堆。 概述 堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。 堆的定義如下：具有n個(gè)元素的序列(k1,k2,...,kn), 當(dāng)且僅當(dāng)滿足: showImg(https://segmentfault...
閱讀 2645·2021-09-13 10:26
閱讀 1907·2021-09-03 10:28
閱讀 1977·2019-08-30 15:44
閱讀 794·2019-08-29 14:07
閱讀 386·2019-08-29 13:12
閱讀 2144·2019-08-26 11:44
閱讀 2337·2019-08-26 11:36
閱讀 2003·2019-08-26 10:19
