前言
之前小六六一直覺得自己的算法比較菜，算是一個短闆吧，以前刷題也還真是三天打魚，兩天曬網，刷幾天，然後就慢慢的不堅持了，是以這次，借助平台的活動，打算慢慢的開始開刷，并且自己還會給刷的題總結下，談談自己的一些思考，和自己的思路等等，希望對小夥伴能有所幫助吧，也可以借此機會把自己短闆補一補，希望自己能堅持下去呀
連結清單的合集
- 六六力扣刷題哈希表之哈希理論
- 六六力扣刷題哈希表之有效的字母異位詞
- 六六力扣刷題哈希表之兩個數組的交集
- 六六力扣刷題哈希表之快樂數
- 六六力扣刷題哈希表之贖金信
- 六六力扣刷題哈希表之三數之和
字元串
- 六六力扣刷題字元串之反轉字元串
- 六六力扣刷題字元串之反轉字元串2
- 六六力扣刷題字元串之替換空格
- 六六力扣刷題字元串之反轉字元串中的單詞
- 六六力扣刷題字元串之找出字元串中第一個比對項的下
- 六六力扣刷題字元串之重複的子字元串
雙指針
- 六六力扣刷題雙指針之移除元素
- 六六力扣刷題雙指針之删除連結清單的倒數第N個節點
- 六六力扣刷題雙指針之連結清單相交
- 六六力扣刷題雙指針之三數之和
- 六六力扣刷題雙指針之反轉連結清單
搜尋二叉樹
- 六六力扣刷題二叉樹之基礎
- 六六力扣刷題二叉樹之遞歸周遊
- 六六力扣刷題二叉樹之疊代周遊
- 六六力扣刷題二叉樹之層序周遊
題目
給你一棵二叉樹的根節點 root ，翻轉這棵二叉樹，并傳回其根節點。
示例 1：
輸入：root = [4,2,7,1,3,6,9]
輸出：[4,7,2,9,6,3,1]
示例 2：
輸入：root = [2,1,3]
輸出：[2,3,1]
示例 3：
輸入：root = []
輸出：[]
思路
我們在做二叉樹題目時候，第一想到的應該是用 遞歸 來解決。
仔細看下題目的 輸入 和 輸出，輸出的左右子樹的位置跟輸入正好是相反的，于是我們可以遞歸的交換左右子樹來完成這道題。
其實就是交換一下左右節點，然後再遞歸的交換左節點，右節點
我們可以總結出遞歸的兩個條件如下：
- 終止條件：目前節點為 null 時傳回
- 交換目前節點的左右節點，再遞歸的交換目前節點的左節點，遞歸的交換目前節點的右節點
class Solution {
public TreeNode invertTree(TreeNode root) {
//遞歸函數的終止條件，節點為空時傳回
if(root==null) {
return null;
}
//下面三句是将目前節點的左右子樹交換
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//遞歸交換目前節點的 左子樹
invertTree(root.left);
//遞歸交換目前節點的 右子樹
invertTree(root.right);
//函數傳回時就表示目前這個節點，以及它的左右子樹
//都已經交換完了
return root;
}
} 疊代
- 判斷其左子樹是否為空，不為空就放入隊列中
- 判斷其右子樹是否為空，不為空就放入隊列中
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) {
return null;
}
//将二叉樹中的節點逐層放入隊列中，再疊代處理隊列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
//每次都從隊列中拿一個節點，并交換這個節點的左右子樹
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果目前節點的左子樹不為空，則放入隊列等待後續處理
if(tmp.left!=null) {
queue.add(tmp.left);
}
//如果目前節點的右子樹不為空，則放入隊列等待後續處理
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
//傳回處理完的根節點
return root;
}
}