題目一覽：
606. 根據二叉樹創建字符串 - 力扣（LeetCode）
506. 相對名次 - 力扣（LeetCode）
1. 兩數之和 - 力扣（LeetCode）
100. 相同的樹 - 力扣（LeetCode）
101. 對稱二叉樹 - 力扣（LeetCode）
這是周一截止到今天周五的，這次選的題目都比較簡單。大部分都和二叉樹用dfs解題有關（因為前一整子學了這些，剛好就再寫一遍），有一道是關于最近學的堆排序。
題解：
1. 根據二叉樹創建字符串
給你二叉樹的根節點?root?，請你采用前序遍歷的方式，將二叉樹轉化為一個由括號和整數組成的字符串，返回構造出的字符串。
空節點使用一對空括號對?"()"?表示，轉化后需要省略所有不影響字符串與原始二叉樹之間的一對一映射關系的空括號對。
解：這道題的關鍵是明白什么時候存放root.val，什么時候存放? “（）” ，“（ ” ，? “? ）”
1）創建StringBuilde類型的對象stringbuilder，之后得到結果都可以通過append操作一步步添加到stringbuilder中。
2）遍歷二叉樹（遞歸）:?
a. 需要分別判斷左子樹和右子樹的情況，當 root 不為空，則將 root.val 放到stringbuilder中。
b. 再去看左子樹情況 ——> 判斷 root.left 是否為空，不為空就將“（ ” 放到stringbuilder中，代表有左子樹，再將左子樹的根放入函數進行遞歸，重復上面的操作。而如果 root.left 為空，就需要判斷右子樹，右子樹也為空，則直接返回，不為空則將“（）” 放入stringbuilder再返回。
c. 判斷右子樹的情況的代碼邏輯則和左子樹一致。唯一不同的是如果判斷右子樹為空的話，不用再去判斷左子樹是否為空，而是直接返回。
d. 最后得到結果stringbuilder，輸出即可
注意：在每次遞歸返回時，“ ）”都會放入stringbuilder。不需要在其他地方再加多余的 “）”。（不太明白的話可以看看代碼理解）
代碼：
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public String tree2str(TreeNode root) { StringBuilder stringBuilder = new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode root,StringBuilder stringBuilder){if(root == null){return;}stringBuilder.append(root.val);//判斷左子樹的情況if(root.left!=null){stringBuilder.append("(");tree2strChild(root.left,stringBuilder);stringBuilder.append(")");}else{if(root.right!=null){stringBuilder.append("()");}else{return;}}//判斷右子樹的情況if(root.right!=null){stringBuilder.append("(");tree2strChild(root.right,stringBuilder);stringBuilder.append(")");} else{return;}}
}2. 相對名次
給你一個長度為?n?的整數數組?score?，其中?score[i]?是第?i?位運動員在比賽中的得分。所有得分都?互不相同?。
運動員將根據得分?決定名次?，其中名次第?1?的運動員得分最高，名次第?2?的運動員得分第?2?高，依此類推。運動員的名次決定了他們的獲獎情況：
- 名次第?
1?的運動員獲金牌?"Gold Medal"?。 - 名次第?
2?的運動員獲銀牌?"Silver Medal"?。 - 名次第?
3?的運動員獲銅牌?"Bronze Medal"?。 - 從名次第?
4?到第?n?的運動員，只能獲得他們的名次編號（即，名次第?x?的運動員獲得編號?"x"）。
使用長度為?n?的數組?answer?返回獲獎，其中?answer[i]?是第?i?位運動員的獲獎情況。
解：這道題的思路很簡單，首先要得到名次，就需要排序。然后對照原數組，按照對應的位置給出排名情況。一開始寫的是得到一個排完序的數組，然后兩個for循環嵌套，一個個對照，結果放進answer數組，但是這樣做會超出時間限制，時間復雜度為O(n^2)，所以后面又用到了哈希表，這樣就可以快速得到對應鍵值的在原數組的下標。
1）這里為了鞏固學習的新知識，排序采用了堆排序。
a. 首先將原數組復制一份，再將復制的數組變成小根堆。
b. 每次將堆頂元素和最后一個元素交換，再將堆數組的長度減1，把其余的部分再進行siftdown，變成小根堆后，重復交換操作和長度減1，以及siftdown操作，以此完成堆排序。
2）哈希表存好原數組以及對應的原始下標，將排完序的數組的值循環給哈希表，得到原始位置，將名次按照原始位置放入answer數組中即可。
代碼：
//1.用堆排序，將數組排成降序
//2.將在ret數組中找到score數組中數據所在的下標名次就是i+1
//3.創建answer數組，將對比出來的結果依次放入answers數組class Solution {int[] ret;public void siftDown(int parent,int usedSize){int child = 2 * parent + 1;while(child < usedSize){//child是否需要換位置if(child + 1 < usedSize && ret[child] > ret[child+1]){child++;}if(ret[child] < ret[parent]){int temp;temp = ret[child];ret[child] = ret[parent];ret[parent] = temp;parent = child;child = 2 * parent + 1;}else{break;}}}public void heapSort(int end){while(end > 0){int temp;temp = ret[end];ret[end] = ret[0];ret[0] = temp;siftDown(0,end);end--;}}public String[] findRelativeRanks(int[] score) {//為防止超時（一開始使用兩個for循環嵌套得answer數組超時了...），使用哈希表Map<Integer,Integer> scoreIndexMap = new HashMap<>();for(int i = 0;i < score.length;i++){scoreIndexMap.put(score[i],i);}String[] answer = new String[score.length]; ret = Arrays.copyOf(score,score.length);int child = ret.length-1;int parent = (child-1)/2;for(int i = parent ; i >= 0 ; i--){siftDown(i,ret.length);}//創建好小根堆后，使用堆排序(降序)heapSort(score.length-1);for(int i = 0;i < ret.length;i++){//找到對應位置int originalIndex = scoreIndexMap.get(ret[i]);if(i == 0){answer[originalIndex] = "Gold Medal";}else if(i == 1){answer[originalIndex] = "Silver Medal";}else if(i == 2){answer[originalIndex] = "Bronze Medal";}else{answer[originalIndex] = String.valueOf(i+1);}}return answer;}
}3.兩數之和
給定一個整數數組?nums?和一個整數目標值?target，請你在該數組中找出?和為目標值?target? 的那?兩個?整數，并返回它們的數組下標。
你可以假設每種輸入只會對應一個答案，并且你不能使用兩次相同的元素。
你可以按任意順序返回答案。
解：這里一開始用的是暴力解法，兩個循環嵌套遍歷即可。降低時間復雜度可以使用哈希表，提供利用哈希表的解法。
1）遍歷nums數組，將target - nums[ i ] 給哈希表，查看哈希表是否存在對應的數，如果咩有就將num[ i ] 和 i 放進哈希表，然后繼續判斷。
這里的巧妙就在于哈希表并沒有一開始就放入數據，而是在遍歷過程一步步將數據放入哈希表。
代碼：
class Solution {public int[] twoSum(int[] nums, int target) {//為了降低時間復雜度，采用哈希表Map<Integer,Integer> hashtable =new HashMap<>();for(int i = 0;i<nums.length;i++){//在哈希表中查找是否存在target-nums[i]，如果有就把位置返回if(hashtable.containsKey(target - nums[i])){return new int[]{hashtable.get(target-nums[i]),i};}hashtable.put(nums[i],i);}return new int[0];}
}4.相同的樹
給你兩棵二叉樹的根節點?p?和?q?，編寫一個函數來檢驗這兩棵樹是否相同。
如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。
解：弄清true和false的情況，同時遍歷兩棵樹即可。
1）true：
a. 兩顆樹都為null
b. 節點的值相同（如果節點的值相同，則可以進行下一步，而不是返回true，最終返回true還是要看節點是否同時到了null）
2）false：
a. 一顆樹為空，另一棵樹不為空
b. 節點的值不相同
3）最后返回 左子樹的比較情況&&右子樹的比較情況
代碼：
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;} else if (p == null || q == null) {return false;} else if (p.val != q.val) {return false;} else {return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}}
}5.對稱二叉樹
給你一個二叉樹的根節點?root?， 檢查它是否軸對稱。
解：關鍵在于找到判斷軸對稱的方法，代碼應該怎么寫。（和第4題差不多思想，直接看代碼也可）
1）先判斷root.left 和root.right 是否相等，相等則繼續向下探查，直到出現null 或者二者數值不同時返回true或者false（如果root為null，則直接返回true）
2）再通過遞歸，root.left作為L，root.right作為R，判斷L.left 和 R.right是否相等，以及L.right 和 R.left 是否相等
3）true和false的情況和第4題差不多，可以看代碼理解，最后返回 judge(L.left,R.right) && judge(L.right,R.left)
代碼：
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean judge(TreeNode L,TreeNode R){if(L == null && R == null){return true;}else if(L != null && R == null || L == null && R != null){return false;}else if(L.val != R.val){return false;}//判斷對稱return judge(L.left,R.right) && judge(L.right,R.left);}public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return judge(root.left,root.right);}
}OK，就先這樣
