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